NYoj 712 探寻宝藏[经典动态规划3](河南省第六届省赛)

本文主要是介绍NYoj 712 探寻宝藏[经典动态规划3](河南省第六届省赛)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

/*NYoj 712 探寻宝藏双线程动态规划（经典的动态规划3）还是不太明白，要努力学习.当然，这题还是可以用最小费用最大流来做.也没有学过这个东西，也要学习.
*/
#include<stdio.h>
#include<string.h>
#define max(a,b) a>b?a:b
int dp[52][52][52][52];
main()
{
//    freopen("input.txt","r",stdin);int T;scanf("%d",&T);while(T--){int m,n;scanf("%d%d",&m,&n);int map[52][52];memset(map,0,sizeof(map));memset(dp,0,sizeof(dp));for(int i=1; i<=m; i++)for(int j=1; j<=n; j++)scanf("%d",&map[i][j]);for(int i=1; i<=m; i++){for(int j=1; j<=n; j++){for(int k=1; k<=m; k++){for(int l=1; l<=n; l++){//i can't understand.if((i<m||j<n)&&i<=k&&j<=l) continue;int num=0;num=max(num,dp[i-1][j][k-1][l]);num=max(num,dp[i][j-1][k][l-1]);if(j-1!=l&&i!=k-1)num=max(num,dp[i][j-1][k-1][l]);if(i-1!=k&&j!=l-1)num=max(num,dp[i-1][j][k][l-1]);dp[i][j][k][l]=num+map[i][j]+map[k][l];//printf("%d dp[%d][%d][%d][%d]=%d\n",num,i,j,k,l,dp[i][j][k][l]);}}}}printf("%d\n",dp[m][n][m][n]-map[m][n]);}
}

这篇关于NYoj 712 探寻宝藏[经典动态规划3](河南省第六届省赛)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---