• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# 方格取数

2周前 (04-08) 7次浏览

• `k`为横纵坐标之和, 可以省去一维.
• 这两遍走法是互相无影响的.
• 如果会同时走上同一个坐标, 这个坐标的值就只加一次就好了, 这样就表示了第二走的值为`0`
``````#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
inline int lowbit(int x) { return x & (-x); }
#define ll long long
#define ull unsigned long long
#define pb push_back
#define PII pair<int, int>
#define VIT vector<int>
#define x first
#define y second
#define inf 0x3f3f3f3f
const int N = 15;
int w[N][N];
int f[N << 1][N][N];
int dx[4][2] = { {0, 0}, {0, -1}, {-1, 0}, {-1, -1} };

int main() {
//freopen("in.txt", "r", stdin);
IO;
int n;
cin >> n;
int x, y, c;
while (cin >> x >> y >> c, x || y || c) w[x][y] = c;
for (int k = 2; k <= 2 * n; ++k)
for (int i1 = 1; i1 <= n; ++i1)
for (int i2 = 1; i2 <= n; ++i2) {
int j1 = k - i1, j2 = k - i2;
if (j1 && j1 <= n && j2 && j2 <= n) {
int v = w[i1][j1];
if (i1 != i2) v += w[i2][j2];
int &x = f[k][i1][i2];
for (int p = 0; p < 4; ++p)
x = max(x, f[k - 1][i1 + dx[p][0]][i2 + dx[p][1]] + v);
}
}
cout << f[n << 1][n][n] << 'n';
return 0;
}

``````