首页 > 代码库 > NYOJ712

NYOJ712

2024-08-06 11:12:57   217人阅读

题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=712

来看思路：

我们先弱弱的思考一下，首先我们得先从左上角dp到右下角  然后在从右下角dp到左上角 

这样就很有难度 我们可以把来回的路径一次dp完事 这样就简单了很多

我们可以设三维数组dp[k][i][j]  k表示第几步，i和j分别表示来回两个点的坐标  那么我们就有状态转移方程

dp[k][i][j] = max(max(dp[k-1][i][j],dp[k-1][i-1][j-1]),max(dp[k-1][i-1][j],dp[k-1][i][j-1]));

下面看代码：

#include<stdio.h>#include<string.h>int dp[110][55][55],a[55][55];int max(int a,int b){    return a > b? a:b;}int main(){    int N,n,m,t,i,j,k;    scanf("%d",&N);    while(N--)    {        memset(dp,0,sizeof(dp));        scanf("%d%d",&m,&n);        for(i = 1;i <= m;i++)        {            for(j = 1;j <= n;j++)            {                scanf("%d",&a[i][j]);            }        }        for(k = 3;k < m + n;k++)        {            for(i = 1;i <= m;i++)            {                for(j = i + 1;j <= m;j++)                {                    if(k - i < 1||k - j < 1)break;                    if(i == j)continue;                    if(k - i > n||k - j > n)continue;                    dp[k][i][j] = max(max(dp[k-1][i][j],dp[k-1][i-1][j-1]),max(dp[k-1][i-1][j],dp[k-1][i][j-1]));                    dp[k][i][j] += a[i][k-i] + a[j][k-j];                }            }        }        int t = m + n;        dp[t][m][m] = max(max(dp[t-1][m][m],dp[t-1][m-1][m-1]),max(dp[t-1][m-1][m],dp[t-1][m][m-1]));        printf("%d\n",dp[t][m][m] + a[m][n]);    }    return 0;}

 

NYOJ712


联系
我们