题解 P1006 【传纸条】

· · 题解

管理员大大求通过

例题：

P1004，P1006，P3126,（链接就不贴了）

既然是左上到右下，右下到左上，那就算做左上到右下两次就好啦。

定义

f[step][i][j] 表示当走到横纵坐标和为step时，在i，j这两个纵坐标时（step<=n+m-1，i<j(保证路径不重复)，i<m,j<=m(m为最大纵坐标））的最大收益

Q：step表示什么呢？

A：因为纵横坐标的和相同的点在同一条斜线上，所以step枚举的就是这一条斜线上的所有点

Q：为什么这可行呢？

A：因为i<j，所以我们走过的路径不会重复，满足题意。再有，通过step，我们能够得到每个点的纵横坐标，因此可行。

状态转移

        memset(f,-1,sizeof(f));
    f[2][1][1]=0;
    for(int k=3;k<n+m;k++)//n是行，m是列
        for(int i=1;i<m;i++)
            for(int j=i+1;j<=m;j++)
            {
                int s=f[k][i][j];
                s=max(s,f[k-1][i][j]);
                s=max(s,f[k-1][i][j-1]);
                s=max(s,f[k-1][i-1][j]);
                s=max(s,f[k-1][i-1][j-1]);
                if(s==-1) continue;
            f[k][i][j]=s+a[k-j][j]+a[k-i][i]; 
        }
    printf("%d",f[n+m-1][m-1][m]);

Q：这些方程是从哪里推过来的呢？

A：k-1（就不说了……可以理解）。i与j，因为只能从上面和左面转过来（配图），应该可以理解

手绘，勿喷

答案位置

f[n+m-1][m-1][m]

Q：这个东西在哪里？

A：就在右下角的左边一个和上边一个

P1004代码

#include<cstdio>
#define max(A,B) A<B?B:A
#include<cstring>
int n,m,a[60][60],f[200][60][60];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    memset(f,-1,sizeof(f));
    f[2][1][1]=0;
    for(int k=3;k<m+n;k++)
        for(int i=1;i<m;i++)
            for(int j=i+1;j<=m;j++)
            {
                int s=f[k][i][j];
                s=max(s,f[k-1][i][j]);
                s=max(s,f[k-1][i][j-1]);
                s=max(s,f[k-1][i-1][j]);
                s=max(s,f[k-1][i-1][j-1]);
                if(s==-1) continue;
                f[k][i][j]=s+a[k-j][j]+a[k-i][i]; 
            }
    printf("%d",f[n+m-1][m-1][m]);
    return 0;
 }

鸭维后代码

#include<cstdio>
#define max(A,B) A<B?B:A
#include<cstring>
int n,m,a[60][60],f[60][60];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    memset(f,-1,sizeof(f));
    f[1][1]=0;
    for(int k=3;k<m+n;k++)
        for(int i=m-1;i>=1;i--)//注意这里的方向
            for(int j=m;j>=i+1;j--)
            {
                int s=f[i][j];
                s=max(s,f[i][j]);
                s=max(s,f[i][j-1]);
                s=max(s,f[i-1][j]);
                s=max(s,f[i-1][j-1]);
            if(s==-1) continue;
            f[i][j]=s+a[k-j][j]+a[k-i][i]; 
            }
    printf("%d",f[m-1][m]);
    return 0;
 }

欢迎来踩 博客地址