首页 > 代码库 > 【洛谷P1006】传纸条
【洛谷P1006】传纸条
双线程dp
f [ i ] [ j ] [ k ] [ l ] 表示 走到 (i,j),返回时走到(k,l)时的(总)最大价值
1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 const int N=52; 5 int f[N][N][N][N],a[N][N],n,m; 6 int max(int x,int y){ 7 return x>y?x:y; 8 } 9 int main(){ 10 int p,q; 11 scanf("%d %d",&n,&m); 12 for (int i=1;i<=n;i++) 13 for (int j=1;j<=m;j++) 14 scanf("%d",&a[i][j]); 15 for (int i=1;i<=n;i++) 16 for (int j=1;j<=m;j++) 17 for (int k=1;k<=n;k++) 18 for (int l=1;l<=m;l++){ 19 p=max(f[i-1][j][k-1][l],f[i-1][j][k][l-1]); 20 q=max(f[i][j-1][k-1][l],f[i][j-1][k][l-1]); 21 f[i][j][k][l]=max(p,q); 22 f[i][j][k][l]+=a[i][j]+a[k][l]; 23 if (i==k&&j==l) 24 f[i][j][k][l]-=a[i][j]; 25 } 26 printf("%d",f[n][m][n][m]); 27 return 0; 28 }
【洛谷P1006】传纸条
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。