Logo CloudLunar

CodeVS/1169
2014年12月8日 (一) 16:47云璟月（讨论 | 贡献）的版本

(差异) ←上一版本 | 最后版本 (差异) | 下一版本→ (差异)

摘要

题目链接 难度等级 完成状态 完成分数 最后编辑时间 失误原因（初次提交分数）
传纸条 ★☆☆☆☆ 答案正确 100 2014/11/28 20:21:12 算法错误（20）

题意

从(1,1)传纸条到(n,m)并返回，每个点只能经过一遍，求好感度最大值。

题解

  • 只可以向下或者向右，阶段性仍然很明显，首先想到的是一遍一遍传纸条，相当于传两遍，但是这是有后效性的（见第一段代码），所以必须两遍一起走。
  • 一开始纠结于这种传递，两个点虽然来源不同，但是其祖先的来源相同。
显示/移除行号
  1. o - o - o
  2.     |   |
  3.     o   o - o
  4.     |       
  5.     o - o
  • 但是这种情况出现的前提是出现：
显示/移除行号
  1. o - o - o
  2.     |
  3.     o
  • 因此只要一直不允许一个点延伸出两条路就可以了
  • 每次分别枚举两个点从左、上转移状态，然后两次被转移的点和转移到的点都不应该相同。对于一个点，可以通过枚举i+j来分阶段，以省去一个维度：
显示/移除行号
  1. dp[i][j][sum]=v[i][sum-i]+v[j][sum-j]+
  2.     max{
  3.         dp[i-1][j][sum-1]+
  4.         dp[i][j-1][sum-1]+
  5.         dp[i-1][j-1][sum-1]+
  6.         dp[i][j][sum-1]
  7.     };
  8. //dp[i][j][sum]表示两条路线分别走到(i,sum-i)(j,sum-j)时候的最大好感度

代码

1169（记忆化搜索，错误写法）.cpp代码已折叠
展开折叠内容
显示/移除行号
  1. #include<cstdio>
  2. int M[100][100][3]={},used[100][100]={},n,m,v[100][100];
  3. void dfs(const int &x,const int &y,const int &t,const int &c)
  4. {
  5.     if(used[x][y])
  6.         return;
  7.     if((!(x==1&&y==1))&&(!(x==n&&y==m)))
  8.         used[x][y]=1;
  9.     if(M[x][y][t]>c&&M[x][y][t])return;
  10.     M[x][y][t]=c;
  11.     if(x==n&&y==m)
  12.     {
  13.         if(t==1)
  14.             dfs(1,1,2,c);
  15.         return;
  16.     }
  17.     if(x+1<=n)
  18.         dfs(x+1,y,t,c+v[x+1][y]);
  19.     if(y+1<=m)
  20.         dfs(x,y+1,t,c+v[x][y+1]);
  21.     used[x][y]=0;
  22. }
  23. int main()
  24. {
  25.     scanf("%d%d",&n,&m);
  26.     for(int i=1;i<=n;++i)
  27.     {
  28.         for(int j=1;j<=m;++j)
  29.         {
  30.             scanf("%d",&v[i][j]);
  31.         }
  32.     }
  33.     dfs(1,1,1,v[1][1]);
  34.     printf("%d\n",M[n][m][2]-v[n][m]);
  35.     return 0;
  36. }
1169.cpp代码已折叠
展开折叠内容
显示/移除行号
  1. #include<cstdio>
  2. #include<algorithm>
  3. using namespace std;
  4. int m,n,dp[100][100][200]={},v[100][100]={};
  5. int main()
  6. {
  7.     scanf("%d%d",&m,&n);
  8.     for(int i=1;i<=m;++i)
  9.         for(int j=1;j<=n;++j)
  10.             scanf("%d",&v[i][j]);
  11.     for(int sum=2;sum<n+m;++sum)
  12.         for(int i=max(1,sum-n);i<=min(sum-1,m);++i)
  13.             for(int j=max(1,sum-n);j<=min(sum-1,m);++j)
  14.             {
  15.                 if(i==j)continue;
  16.                 if(i-1!=j)
  17.                     dp[i][j][sum]=max(dp[i][j][sum],dp[i-1][j][sum-1]+v[i][sum-i]+v[j][sum-j]);
  18.                 if(i!=j-1)
  19.                     dp[i][j][sum]=max(dp[i][j][sum],dp[i][j-1][sum-1]+v[i][sum-i]+v[j][sum-j]);
  20.                 dp[i][j][sum]=max(dp[i][j][sum],dp[i-1][j-1][sum-1]+v[i][sum-i]+v[j][sum-j]);
  21.                 dp[i][j][sum]=max(dp[i][j][sum],dp[i][j][sum-1]+v[i][sum-i]+v[j][sum-j]);
  22.             }
  23.     printf("%d",max(dp[m-1][m][n+m-1],dp[m][m-1][n+m-1]));
  24. }
取自“https://blog.CloudLunar.com/index.php?title=CodeVS/1169&oldid=799”
分享ShareQQ空间新浪微博人人网一键分享TwitterFacebook

著作权声明[编辑]

关于[编辑]