正題

luogu 7472

---

題目大意

給出一個(gè)正方形點(diǎn)陣，讓你選擇兩個(gè)點(diǎn)，分別向兩個(gè)方向移動(dòng)（必須是45度），每到一個(gè)點(diǎn)就得到該點(diǎn)的貢獻(xiàn)（不重復(fù)得），遇到墻壁反射，問(wèn)你最大貢獻(xiàn)

---

解題思路

不難發(fā)現(xiàn)，從每一個(gè)點(diǎn)向任意方向移動(dòng)總會(huì)遇到左邊的邊界，且每個(gè)邊界最多走一遍（有貢獻(xiàn)的），走的路徑如下

那么可以枚舉左邊的邊界，然后向左下角運(yùn)動(dòng)

先處理出每種方案的貢獻(xiàn)，以及和邊界的交點(diǎn)

然后枚舉所選的兩條線，再通過(guò)和邊界的交點(diǎn)得出兩條線的交點(diǎn)，減去即可

---

代碼

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 1010 using namespace std; int n, x, y, xx, yy, ans, s[N], u[N], r[N], d[N], a[N][N]; int js(int x, int y) {int g = 1;if (x == n) g <<= 1;//對(duì)角線if (y == 1) g <<= 1;return (a[x + y >> 1][1 + (x - y >> 1)] + a[1 + (u[x] - u[y] >> 1)][u[x] + u[y] >> 1] + a[r[y] + r[x] >> 1][n - (r[y] - r[x] >> 1)] + a[n - (d[y] - d[x] >> 1)][d[y] + d[x] >> 1]) / g;//減去交點(diǎn) } int main() {scanf("%d", &n);for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j)scanf("%d", &a[i][j]);for (int i = 1; i <= n; ++i){x = i;y = 1;xx = 1;yy = 1;if (i == 1) u[i] = 1;if (i == n){d[i] = 1;xx = -1;}s[i] = a[x][y];x += xx;y += yy;while(x != i || y != 1){if (x == n) xx = -1, d[i] = y;//找和邊界的交點(diǎn)if (x == 1) xx = 1, u[i] = y;if (y == n) yy = -1, r[i] = x;s[i] += a[x][y];if ((x == 1 || x == n) && (y == 1 || y == n)) break;x += xx;y += yy;}for (int j = 1; j < i; ++j){if ((i + j) & 1) ans = max(ans, s[i] + s[j]);//如果距離為奇數(shù)那么不相交在整點(diǎn)上else ans = max(ans, s[i] + s[j] - js(i, j));}}printf("%d", ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的吃豆人（luogu 7472/NOI Online 2021 普及组 T2）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。