CodeVS/1169

摘要

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

题意

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

题解

• 只可以向下或者向右，阶段性仍然很明显，首先想到的是一遍一遍传纸条，相当于传两遍，但是这是有后效性的（见第一段代码），所以必须两遍一起走。
• 一开始纠结于这种传递，两个点虽然来源不同，但是其祖先的来源相同。

o - o - o
    |   |
    o   o - o
    |       
    o - o

• 但是这种情况出现的前提是出现：

o - o - o
    |
    o

• 因此只要一直不允许一个点延伸出两条路就可以了
• 每次分别枚举两个点从左、上转移状态，然后两次被转移的点和转移到的点都不应该相同。对于一个点，可以通过枚举i+j来分阶段，以省去一个维度：

dp[i][j][sum]=v[i][sum-i]+v[j][sum-j]+
    max{
        dp[i-1][j][sum-1]+
        dp[i][j-1][sum-1]+
        dp[i-1][j-1][sum-1]+
        dp[i][j][sum-1]
    };
//dp[i][j][sum]表示两条路线分别走到(i,sum-i)(j,sum-j)时候的最大好感度

代码

1169（记忆化搜索，错误写法）.cpp代码已折叠 展开折叠内容

#include<cstdio> int M[100][100][3]={},used[100][100]={},n,m,v[100][100]; void dfs(const int &x,const int &y,const int &t,const int &c) { if(used[x][y]) return; if((!(x==1&&y==1))&&(!(x==n&&y==m))) used[x][y]=1; if(M[x][y][t]>c&&M[x][y][t])return; M[x][y][t]=c; if(x==n&&y==m) { if(t==1) dfs(1,1,2,c); return; } if(x+1<=n) dfs(x+1,y,t,c+v[x+1][y]); if(y+1<=m) dfs(x,y+1,t,c+v[x][y+1]); used[x][y]=0; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j) { scanf("%d",&v[i][j]); } } dfs(1,1,1,v[1][1]); printf("%d\n",M[n][m][2]-v[n][m]); return 0; }

1169.cpp代码已折叠 展开折叠内容

#include<cstdio> #include<algorithm> using namespace std; int m,n,dp[100][100][200]={},v[100][100]={}; int main() { scanf("%d%d",&m,&n); for(int i=1;i<=m;++i) for(int j=1;j<=n;++j) scanf("%d",&v[i][j]); for(int sum=2;sum<n+m;++sum) for(int i=max(1,sum-n);i<=min(sum-1,m);++i) for(int j=max(1,sum-n);j<=min(sum-1,m);++j) { if(i==j)continue; if(i-1!=j) dp[i][j][sum]=max(dp[i][j][sum],dp[i-1][j][sum-1]+v[i][sum-i]+v[j][sum-j]); if(i!=j-1) dp[i][j][sum]=max(dp[i][j][sum],dp[i][j-1][sum-1]+v[i][sum-i]+v[j][sum-j]); dp[i][j][sum]=max(dp[i][j][sum],dp[i-1][j-1][sum-1]+v[i][sum-i]+v[j][sum-j]); dp[i][j][sum]=max(dp[i][j][sum],dp[i][j][sum-1]+v[i][sum-i]+v[j][sum-j]); } printf("%d",max(dp[m-1][m][n+m-1],dp[m][m-1][n+m-1])); }