摘要

题目链接 难度等级 完成状态 完成分数 最后编辑时间 失误原因(初次提交分数)
传纸条 ★☆☆☆☆ 答案正确 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]));
}

著作权声明[编辑]

关于[编辑]