P1004 [NOIP2000 提高组] 方格取数
将先后两次路线当作一次走两条路，路线可以重复，但价值只能计数一次
k = i1 + j1 = i2 + j2
以下分别对每一步作了详细的注释
#include <iostream>
#include <algorithm>using namespace std;
const int N = 10 + 9;int n,m;
int g[N][N];
int f[2* N][N][N];void solve()
{int x,y,w;cin >> n;while(cin >> x >> y >> w,x || y || w) g[x][y] = w;for (int k = 2;k <= 2 * n;k ++) //k代表横纵坐标之和;初值为2:A点坐标为(1,1),截止为2 * n:B点坐标为(n,n)for (int i1 = 1;i1 <= n;i1 ++)for (int i2 = 1;i2 <= n;i2 ++){int j1 = k - i1,j2 = k - i2;//t => 价值int t = g[i1][j1];if (i1 != i2) t += g[i2][j2]; //两次走相同的方块，价值只算一次int &x = f[k][i1][i2];//上一步的情况x = max(x,f[k - 1][i1 - 1][i2 - 1] + t);//都从上过来x = max(x,f[k - 1][i1 - 1][i2] + t);//从上，从左过来x = max(x,f[k - 1][i1][i2 - 1] + t);//从左，从上过来x = max(x,f[k - 1][i1][i2] + t);//都从左过来}cout << f[2 * n][n][n] << endl;
}int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _ = 1;while(_--) solve();return 0;
}