首页 > 代码库 > NYOJ712
NYOJ712
题目链接: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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。