51nod 1084+1083 矩阵取数问题 dp

刺骨的言语ヽ痛彻心扉 2022-08-20 12:26 22阅读 0赞

先来说这个比较简单的问题：

一个N\*N矩阵中有不同的正整数，经过这个格子，就能获得相应价值的奖励，从左上走到右下，只能向下向右走，求能够获得的最大价值。

例如：3 \* 3的方格。

1 3 3

2 1 3

2 2 1

能够获得的最大价值为：11。

经典并且简单的问题，dp\[i\]\[j\]表示的是从位置(1,1)到位置(n,n)的最大价值。

#include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    int const maxn = 505 ;
    int a[maxn][maxn];
    int dp[maxn][maxn] ;
    //dp[i][j]表示的是从位置(1,1)到位置(i,j)所获得的最大价值
    
    int main()
    {
        int n;
        while(scanf("%d",&n)!=EOF)
        {
            memset(dp,0,sizeof(dp));
            for(int i = 1 ; i <= n ; i++)
            {
                for(int j = 1 ; j <= n ; j++)
                {
                    scanf("%d",&a[i][j]);
                }
            }
            for(int i = 1 ; i <= n ; i++)
            {
                for(int j = 1 ; j <=n ; j++)
                {
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1])+a[i][j] ;
                }
            }
            printf("%d\n",dp[n][n]);
        }
        return 0;
    }

比较麻烦的是第二个问题：

一个M\*N矩阵中有不同的正整数，经过这个格子，就能获得相应价值的奖励，先从左上走到右下，再从右下走到左上。第1遍时只能向下和向右走，第2遍时只能向上和向左走。两次如果经过同一个格子，则该格子的奖励只计算一次，求能够获得的最大价值。

例如：3 \* 3的方格。

1 3 3

2 1 3

2 2 1

这个问题就不是和上面的一样了，要求的是先到右下角然后返回左上角的最大价值，并且要是经过相同的位置该位置的价值只能取一次。

从左上角到右下角再回到左上角，这个过程可以看作从左上角同时走两路到右下角，我们记录两路当前的位置，这样就可以处理“同一个格子的数只能取一次”了。

1. 假设是m行, n列的矩阵，那么从左上角，走到右下角，需要的步数就是, (m + n)步；当有两条路径的时候，也就是i + j = p + q  
   2. 保证两条线不相交:  
     假设下一个目标节点是(i, j, p, q)那么需要推导的点就是  
     (i - 1, j) (p - 1, q)  
     (i, j - 1) (p, q - 1)  
   
     因此 max(dp\[i - 1\]\[j\]\[p - 1\]\[q\], dp\[i - 1\]\[j\]\[p\]\[q - 1\],  
              dp\[i\]\[j - 1\]\[p - 1\]\[q\], dp\[i\]\[j - 1\]\[p\]\[q - 1\]) + val\[i\]\[j\] + val\[p\]\[q\]  
  3. 优化:  
     因为知道步数之后, 知道行坐标, 即可推算出纵坐标  
     那么, 优化后的dp方程为  
     k = i + j = p + q  
   
     其实需要判定列的原因是为了\`取\`val中的值  
     j = k - i;  
     q = k - q;  
       
     那么对于行 存在两种可能 (i - 1, p) (i, p - 1), (i - 1, p - 1), (i, j)  最后一种情况是, 列变化了  
     dp\[k\]\[i\]\[p\] = max (dp\[k - 1\]\[i - 1\]\[p\], dp\[k - 1\]\[i\]\[p - 1\], dp\[k - 1\]\[i - 1\]\[p - 1\], dp\[k - 1\]\[i\]\[p\]) + val\[i\]\[j\] + val\[p\]\[q\]  
     其中i != p

#include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    int const maxn = 205 ;
    int a[maxn][maxn];
    int dp[2*maxn][maxn][maxn] ;
    //dp[k][x1][x2] k是步数，x1是第一个走法的横坐标，x2是第二种走法的横坐标
    
    int main()
    {
        int n,m ;
        while(scanf("%d%d",&m,&n)!=EOF)
        {
            memset(a,0,sizeof(a));
            for(int i = 1 ; i <= n ; i++)
            {
                for(int j = 1 ; j <= m ; j++)
                {
                    scanf("%d",&a[i][j]);
                }
            }
            memset(dp,0,sizeof(dp));
            int d ;
            for(int x1 = 1 ; x1 <= n ; x1++)
            {
                for(int x2 = 1 ; x2 <= n ; x2++)
                {
                    for(int k = max(x1,x2)+1 ; k <= min(x1,x2)+m ; k++)
                    {
                        if(x1!=x2)d = a[x1][k-x1]+a[x2][k-x2] ;
                        else d = a[x1][k-x1] ;
                        dp[k][x1][x2] = max(dp[k-1][x1-1][x2],max(dp[k-1][x1][x2-1],max(dp[k-1][x1-1][x2-1],dp[k-1][x1][x2])))+d;
                        //cout<<dp[k][x1][x2]<<endl;
                    }
                }
            }
            printf("%d\n",dp[m+n][n][n]);
        }
        return 0 ;
    }

PS：其实还做过一个类似的dp题目，要求的是计算从左上角走到右下角以及从左上角走到右上角的总价值的最大值，其中两条路可以不同步，并且经过的同一个位置的价值变为0.

具体看连接[点击打开链接][Link 1]

[Link 1]: http://blog.csdn.net/liuyanfeier/article/details/50543743