题目描述
摘花生, 但是走两次; 很容易想到贪心, 即每次都取得尽可能大, 取两次就很简单了. 但实际上这样不一定能够得到最优解, 接下来举出反例
反例
1 2 1
2 3 2
3 2 1
在这个例子中第一次可以(1, 1) -> (2, 1) -> (2, 2) -> (3, 2) -> (3, 3)
第二次(1, 1) -> (1, 2) -> (1, 3) -> (2, 3) -> (3, 3)
每次都是最大, 但是最后把左下角的3剩下来了
实际上在整体总和相同的情况下, 应该是把右上角的1剩下才是最优解
算法
所以要一起走, 设两个路线一起一格一格向(n, n)推进, 中间可能分别处于不同的位置设为(i1, j1), (i2, j2), 状态可以表示为f[i1][j1][i2][j2], 表示当处于这两点时可以取到的最大值
但由于路线1和路线2走过的格数一定相同, i1 + j1 = i2 + j2 = c, 所以可以记录坐标之和, 将4维转为3维:
f[c][i1][i2], j1, j2通过计算得到.
每次处理有四种情况, 对应两个路线往右往下的四种组合, 同时要处理重合的情况, 避免重复两条路线重复计算, 即 i1 == i2 的情况
C++ 代码
#include <iostream>
using namespace std;
const int N = 15;
int f[N * 2][N][N];
int n;
int w[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 && j2 >= 1)
{
int t = w[i1][j1] + w[i2][j2];
if (i1 == i2) t >>= 1;// 重合只能算一个
int &x = f[k][i1][i2];
x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);// 同时从上面来
x = max(x, f[k - 1][i1][i2] + t);// 同时从左边来
x = max(x, f[k - 1][i1 - 1][i2] + t);// 一左一上
x = max(x, f[k - 1][i1][i2 - 1] + t);// 一左一上
}
}
printf("%d", f[n + n][n][n]);
}