NYOJ61 传纸条（一）双线程dp-白红宇

NYOJ61 传纸条（一）双线程dp

阅读量：6292 次

发布时间：2019-06-22

本文共 1170 字，大约阅读时间需要 3 分钟。

题意：

从左上向右下传纸条，再传回来，经过不同的路径

中间每个人都有一个好心程度

问最大的好心程度

思路：

去了再回来就等于直接走两遍不同的路径

三维dp

第一维记走了多少步

第二维记第一条路径的纵坐标

第三维记第二条路径的纵坐标

优化了一下32ms过掉

/* ***********************************************Author        :devilCreated Time  :2016/5/25 15:49:13************************************************ */#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               #include 
               
                using namespace std;const int N=51;int dp[N<<1][N][N],mp[N][N];int main(){ //freopen("in.txt","r",stdin); int t,n,m,y1,y2; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&mp[i][j]); dp[3][1][2]=0; for(int l=3;l<=n+m;l++) { for(int i=1;i
                
                 m) continue; for(int j=i+1;j<=n;j++) { y2=l-j; if(y2<=0) break; else if(y2>m) continue; dp[l][i][j]=mp[i][y1]+mp[j][y2]+max(dp[l-1][i][j],max(dp[l-1][i-1][j],max(dp[l-1][i][j-1],dp[l-1][i-1][j-1]))); } } } printf("%d\n",max(dp[n+m-1][n][n],max(dp[n+m-1][n-1][n],max(dp[n+m-1][n][n-1],dp[n+m-1][n-1][n-1])))); } return 0;}