Vijos P1493 传纸条 （双线程DP）

分析：这题要把它的隐藏题意YY出来、i+j=x+y、这个找出来了就很容易了、直接开个4维来DP、

#include<stdio.h>
int dp[51][51][51][51];
int num[51][51];
int max(int a,int b,int c,int d)
{
    if(a>b&&a>c&&a>d)return a;
    if(b>a&&b>c&&b>d)return b;
    if(c>b&&c>a&&c>d)return c;
    return d;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&num[i][j]);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            for(int x=1;x<=n;x++)
            {
                int y=i+j-x;
                if(i>x&&y>=0)
                {
                    dp[i][j][x][y]=max(dp[i-1][j][x-1][y]+num[i][j]+num[x][y],dp[i-1][j][x][y-1]+num[i][j]+num[x][y],dp[i][j-1][x-1][y]+num[i][j]+num[x][y],dp[i][j-1][x][y-1]+num[i][j]+num[x][y]);
                }
            }
        }
    }
    printf("%d\n",dp[n][m-1][n-1][m]);
    return 0;
}

Vijos P1493 传纸条 （双线程DP）,布布扣,bubuko.com

Vijos P1493 传纸条 （双线程DP）

原文：http://blog.csdn.net/a1dark/article/details/23143809