进阶:k取方格数(todo)
https://www.acwing.com/problem/content/384/
概览
2-分支路问题,BFS, 搜索路径确定只可能向右或者下,所以DP
题解
对于同一个棋盘,会走两次路,可以扩展到k次,如何考虑?
一个很好的思路:
不管多难,其实总是可以将DP的维度放大使问题得到解决;然后就是涉及到具体的集合划分,以及每种划分然后怎么考虑
- 策略:
> 考虑同时走, f[i1, j1, i2, j2]表示所有从(1,1), (1,1)分别走向(i1,j1), (i2,j2)的路径的最大值。 - 如何处理“同一个格子不能被重复选择”
> 什么时候会重合?考虑第一次重合,当两个路径的横纵坐标相同时重合。
> 集合划分: 可能走的四种路径
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 15;
int n;
int w[N][N];
int f[N * 2][N][N];
int main() {
scanf("%d", &n);
int a, b, c;
while(cin >> a >> b >> c, a || b || c) w[a][b] = c;
for (int k = 2; k <= n + 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 >= 1 && j1 <= n && j2 >= 1 && j2 <= n) {
int t = w[i1][j1];
if (i1 != i2) t += w[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);
}
}
}
}
printf("%d\n", f[n + n][n][n]);
return 0;
}