题解:
时隔了几个月, 再补充一下对这道题的理解, 因为二刷做不出来....qwq
1、f[i][j][k]表示的是两条路径走k步, 第一条路径当前走到了(i, k - i), 第二条路径当前
走到了(j, k - j)的位置上的方案, 是已经在这个位置上的方案.
2、主要是状态转移是需要考虑所有情况的:
什么状态能转移到(i1, k - i1(看成是j1))和(i2, k - i2(看成是j2)):分开来看,
转移到(i1, j1)的状态有:(i1 - 1, j1), (i1, j1 - 1),
能转移到(i2, j2)的状态有:(i2 - 1, j2), (i2, j2 - 1);
所以错排所以可能就有:
(i1 - 1, j1), (i2 - 1, j2) => (i1, j1), (i2, j2), 步长是i1 - 1 + j1 == k - 1
(i1 - 1, j1), (i2, j2 - 1) => (i1, j1), (i2, j2), 步长是i1 - 1 + j1 == k - 1
(i1, j1 - 1), (i2 - 1, j2) => (i1, j1), (i2, j2), 步长是i1 + j1 - 1 == k - 1
(i1, j1 - 1), (i2, j2 - 1) => (i1, j1), (i2, j2), 步长是i1 + j1 - 1 == k - 1
因为i1 + j1 == i2 + j2 == k;
所以i1 - 1 + j1 = k - 1; i1 + j1 - 1 = k - 1;
刚学的时候的题解:
状态表示: f[i][j][step]:从起点开始同时向先后走两次路线到达分别到达(i, step - i), (j, step - j)且两者移动步数均为step的方案
解释下为什么可以这样,
刚开始的时候我也有点猛蔽,只会四维的dp,但这种优化的dp真的要看到可以压缩状态的细节。
首先题目要求从左上角到右下角取完数以后再从右下角到左上角等价于两个人同时从左上角出发,走相同的步数先后顺序不同,你一步我一步的
走,最后走到终点的方案
因从起点到终点的过程是你一步我一步,同一个起点同一个终点所以step可以共用
状态转移方程: f[i1][i2][st] = max(f[i1 - 1][i2][st - 1], f[i1][i2 - 1][st - 1], f[i1 - 1][i2 - 1][st - 1]) + d;
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 20;
int n, a[N][N], f[N][N][N * 2 ];
bool chect(int x)
{
return (x >= 1 && x <= n);
}
int main()
{
cin >> n;
int x, y, z;
while(cin >> x >> y >> z, x || y || z) a[x][y] = z;
for(int st = 1; st <= n * 2; st ++ )
for(int i1 = 1; i1 <= n; i1 ++ )
{
for(int i2 = 1; i2 <= n; i2 ++ )
{
int j1 = st - i1, j2 = st - i2;
if(chect(j1) && chect(j2))
{
int &v = f[i1][i2][st];
int d = a[i1][j1];
if(i1 != i2) d += a[i2][j2];
if(chect(i1 - 1)) v = max(v, f[i1 - 1][i2][st - 1] + d);
if(chect(i2 - 1)) v = max(v, f[i1][i2 - 1][st - 1] + d);
if(chect(i1 - 1) && chect(i2 - 1)) v = max(v, f[i1 - 1][i2 - 1][st - 1] + d);
v = max(f[i1][i2][st - 1] + d, v);
}
}
}
cout << f[n][n][n * 2] << endl;
return 0;
}