Vijos P1493 传纸条（双线程DP）

浏览数：48 / 时间：2015年06月08日

分析：这题要把它的隐藏题意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）,古老的榕树,5-wow.com

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

Vijos P1493 传纸条（双线程DP）