方格取数
题目链接：方格取数
题解：一种容易想到的思路是：采用贪心法对第一次和第二次行走分别做DP，将两次DP的最优解累加即为答案。
但是这种贪心是错误的，因为两次DP均为对局部求最优解（第二次DP是在第一次DP的影响下求出的局部最优解），这两次DP的结果之和不为全局最优解（不满足无后效性），例如：
0 1 0
2 2 2
1 0 0
对于该方格图，按照上述贪心法，第一次DP会选取第二行的3个2，第二次DP只能选取第一行与第三行的其中一个1，但显然最优解为全取，因此无法用贪心解决本题。
上述讨论引导我们对两次行走通过一次DP解决，即让两次行走同时进行，因此设 \(dp[i][j][x][y]\) 为当前第一次行动的下标为 \((i,j)\)，第二次行动的下标为 \((x,y)\) 时，数的最大值。显然 \(i\) 与 \(j\) ，\(x\) 与 \(y\) 之间存在约束关系，即 \(i+j=x+y=k\)，因此有 \(j=k-i,y=k-x\)，则 \(dp[i][j][x][y]\) 等价于 \(dp[i][k-i][x][k-x]\)。
发现第二维与第四维只需要通过 \(k\) 进行维护即可，因此状态表示设为 \(dp[k][i][x]\)，表示当前行动下标和为 \(k\) 时，第一次行动横坐标为 \(i\)，第二次行动横坐标为 \(x\) 时的取数最大值。
对于状态转移，需要考虑四种情况：
- 第一次行动从上方转移过来，第二次行动从上方转移过来，对应状态 \(dp[k-1][i][x]\) （横坐标不变）
- 第一次行动从左方转移过来，第二次行动从上方转移过来，对应状态 \(dp[k-1][i-1][x]\)
- 第一次行动从上方转移过来，第二次行动从左方转移过来，对应状态 \(dp[k-1][i][x-1]\)
- 第一次行动从左方转移过来，第二次行动从左方转移过来，对应状态 \(dp[k-1][i-1][x-1]\)
得到所有状态后，转移时只需要加上两个坐标对应的值即可，这里需要注意有可能两次行动移动到同一位置，这个时候只需要加一次值，需要特别判断一下。最后将上述所有状态取最大值即可。
除此之外 由于 \(k\) 的取值为 \(2-2n\) 因此通过 \(k\) 求下标时需要判断是否在方格图内。
AC代码：
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 15;
int a[N][N];
int dp[N * 2][N][N];
int n;
void solve() {
cin >> n;
while(1) {
int x, y, c;
cin >> x >> y >> c;
if(x == 0 && y == 0 && c == 0) break;
a[x][y] += c;
}
for (int k = 2; k <= n * 2; k ++) {
for (int i = 1; i <= n; i ++) {
for (int x = 1; x <= n; x ++) {
int j = k - i, y = k - x;
int t = a[i][j];
if (i != x) t += a[x][y];
if (j < 1 || j > n || y < 1 || y > n) continue;
int w1 = dp[k - 1][i][x] + t;
int w2 = dp[k - 1][i - 1][x] + t;
int w3 = dp[k - 1][i][x - 1] + t;
int w4 = dp[k - 1][i - 1][x - 1] + t;
dp[k][i][x] = max(dp[k][i][x], max(w1, max(w2, (max(w3, w4)))));
}
}
}
cout << dp[2 * n][n][n] << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
}
传纸条
题目链接：传纸条
题解：这道题与上一道题的区别在于，该题要求第二条路径不能选择第一条路径选过的位置，即两条路径不能存在交点，而上一道题允许两条路径交叉。
然而上一道题的最优解的路径一定不存在交叉的情况，因此这两道题本质相同，下面给出证明。
证明：假设最优解的路径存在交叉，由于第一条路径走过之后使得该位置的权值变为 \(0\)，因此若第二条路径与第一条路径存在交叉，则交叉点在第二次经过时贡献的值为 \(0\)，而第二次不经过该位置而从其他位置到达该位置的下一个点，其贡献值一定大于等于 \(0\)，答案不会变得更差，因此最优解不存在相交情况。
AC代码：
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 55;
int a[N][N];
int dp[N * 2][N][N];
int n, m;
void solve() {
cin >> m >> n;
for (int i = 1; i <= m; i ++) {
for (int j = 1; j <= n; j ++) {
cin >> a[i][j];
}
}
for (int k = 2; k <= m + n; k ++) {
for (int i = 1; i <= m; i ++) {
for (int x = 1; x <= m; x ++) {
int j = k - i, y = k - x;
if (j < 1 || j > n || y < 1 || y > n) continue;
int t = a[i][j];
if (i != x) t += a[x][y];
int w1 = dp[k - 1][i][x] + t;
int w2 = dp[k - 1][i - 1][x] + t;
int w3 = dp[k - 1][i][x - 1] + t;
int w4 = dp[k - 1][i - 1][x - 1] + t;
dp[k][i][x] = max(dp[k][i][x], max(w1, max(w2, max(w3, w4))));
}
}
}
cout << dp[m + n][m][m];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
}