查看CodeVS/1169的源代码 ←CodeVS/1169


[[分类:棋盘动态规划]]
==摘要==
{{信息题|传纸条|http://www.codevs.cn/problem/1169/|1|100|time=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来分阶段，以省去一个维度：
<pre>
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)时候的最大好感度
</pre>
==代码==
{{折叠|1169（记忆化搜索，错误写法）.cpp代码已折叠
|<pre>
#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;
}
</pre>
|code1169}}
{{折叠|1169.cpp代码已折叠
|<pre>
#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]));
}
</pre>
|code1169_2}}