考察: 线性dp
错误思路:
先走一遍,将走过的地方mp标为0
这个算法本蒟蒻想不出来怎么实现....
正确思路:
可以将两次走当作两次一起走.设第一次为A,第二次为B.只要步数相同,A和B的横纵坐标和就会相同.本来是需要4维数组,所以可以优化到三维.
f[k][i][j]表示的就是到mp[i][k-i]和mp[j][k-j]的权值和.i就是A的横坐标,j是B的横坐标.那么如何进行集合划分呢.由摘花生那道题可以想出划分为四类: 1.A从上面来,B从上面来.2.A从左边来,B从上面来...以此类推.
注意: 上一层状态是k-1,不是k-2,k表示的是横纵坐标和
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 using namespace std; 5 const int N = 15; 6 int mp[N][N],f[N+10][N][N]; 7 int main() 8 { 9 int n,x,y,c; 10 scanf("%d",&n); 11 while(scanf("%d%d%d",&x,&y,&c)&&(x+y+c)) mp[x][y] = c; 12 for(int k=2;k<=n+n;k++) 13 for(int i=1;i<=n&&i<k;i++) 14 for(int j=1;j<=n&&j<k;j++) 15 { 16 int a = f[k-1][i-1][j-1],b=f[k-1][i-1][j],c=f[k-1][i][j-1],d=f[k-1][i][j]; 17 f[k][i][j] = max(max(a,b),max(c,d))+mp[j][k-j]; 18 if(i!=j) f[k][i][j]+=mp[i][k-i]; 19 } 20 printf("%d\n",f[n+n][n][n]); 21 return 0; 22 }