在贴出正确解法之前,我先贴出一个我的一个分两步走(先走最大,再走第二大)的错误解法,以免再犯错
错误解法
#include<iostream>
#include<cstring>
using namespace std;
const int N = 15;
int n, r, c, num;
int f[N][N], backup[N][N];
//记录转移过来的上一个状态
pair<int,int> state[N][N];
int cnt;
int main() {
cin >> n;
while(cin >> r >> c >> num, r || c || num) {
f[r][c] = num;
}
memcpy(backup, f, sizeof f);
int res = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(f[i - 1][j] > f[i][j - 1]) {
state[i][j] = {i - 1, j};
f[i][j] += f[i - 1][j];
}else{
state[i][j] = {i, j - 1};
f[i][j] += f[i][j - 1];
}
}
}
//置空最大路径上已经取走的数
int i = n, j = n;
while(i || j) {
int x = i, y = j;
backup[i][j] = 0;
i = state[x][y].first, j = state[x][y].second;
}
for(i = 1; i <= n; i++) {
for(j = 1; j <= n; j++) {
backup[i][j] += max(backup[i - 1][j], backup[i][j - 1]);
}
}
cout << backup[n][n] + f[n][n] << endl;
}
不能通过的样例
7
1 3 2
1 4 3
2 3 3
3 3 3
5 5 4
6 5 4
7 3 2
7 5 4
0 0 0
输出:23
正确输出:25
解释
这是一种类似贪心的解法,第一次选择最大的,然后把最大路径上的数字都置为空,第二次再选择最大的。
但这种解法有一种问题,第一次选择最大的时候,可能会影响第二次的选择,导致了整体的最优受到影响。为了让整体的值更大,所以我们得小心地选,尽量避免影响第二条路径。因此这第一次选择的路径不一定是值最大的路径。
所以这种二次选择的解法是不可行的。
正确解法
状态表示
考虑两条路径同时走的情况,用$f[i_1][j_1][i_2][j_2]$表示第一条路径走到$i_1,j_1$, 第二条路径走到$i_2,j_2$位置的取数最大值,那么很显然,结果就是$f[n][n][n][n]$, 其中i
,j
分别是行号和列号
这个状态可以进一步化简,用k来表示某条路径的行号和列号之和,比如一条路径为$i_1 + j_1$,这样状态表示就压缩到了三维$f[k][i_1][i_2]$,其中$i_1$表示第一条路径的行号,$i_2$表示第二条路径的行号
可以依次枚举$k,i_1,i_2$,这样就可以得到每条路径的行号和列号
状态转移
有了状态表示,那么状态转移就很好想了。因为这两条路径都只可以往下走或者往右走,所以当前状态的上一个状态不外乎四种情况
- 第一条路径往下走,第二条路径往下走, 即$f[k - 1][i_1 - 1][i_2 - 1]$
- 第一条路径往下走,第二条路径往右走,即$f[k - 1][i_1 - 1][i_2]$
- 第一条路径往右走,第二条路径往右走,即$f[k - 1][i_1][i_2]$
- 第一条路径往右走,第二条路径往下走,即$f[k - 1][i_1][i_2 - 1]$
此外需要注意的一点,k并不是指两条路径的路径和,它只表示了上一种状态
因为i和j最小时,k = 2,i和j最大时,k = n + n,所以k的总的状态范围为2到n + n
记上一个状态走到当前状态取数为t,那么如果这两条路径在当前这个点相交时,即$i_1 = i_2, j_1 = j_2$时,那么取数$t = w[i_1][j_1]$, 否则为$t = w[i_1][j_1] + w[i_2][j_2]$
拿t分别加上上一种状态的四种情况,取个max就是当前状态的最大值
#include<iostream>
#include<cstring>
using namespace std;
const int N = 15;
int n, r, c, num;
int f[N + N][N][N], w[N][N];
int main() {
cin >> n;
while(cin >> r >> c >> num, r || c || num) {
w[r][c] = num;
}
//k表示其中两条路径长度的总和
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) continue;
//要走的路径
int t = w[i1][j1];
if(i1 != i2) t += w[i2][j2];
int& x = f[k][i1][i2];
x = max(x, t + f[k - 1][i1 - 1][i2 - 1]); //上一个状态的两条路径分别往下走一格
x = max(x, t + f[k - 1][i1][i2 - 1]);
x = max(x, t + f[k - 1][i1 - 1][i2]);
x = max(x, t + f[k - 1][i1][i2]);
}
}
}
cout << f[n + n][n][n] << endl;
return 0;
}
我太笨了,还是不太理解k的用处
请问为什么要加&?我不懂呜呜
很详细,看明白了
%%%这个题解看懂了为什么不能分两步走
如果分两步走,第一步取最优,第二步是在第一步的影响下的最优,不具有全局最优,所以是错误的
哈哈谢谢了,那天我想了一下又想通了