旧作补档

前言

快考蓝桥杯了，发现自己dp不会，补了几题。
写一篇题解攒攒人品以防爆零

题目描述

小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度之和最大。
第一行有 2 个用空格隔开的整数 m 和 n，表示学生矩阵有 m 行 n 列。
接下来的 m 行是一个 m×n 的矩阵，矩阵中第 i 行 j 列的整数表示坐在第 i 行 j 列的学生的好心程度，每行的 n 个整数之间用空格隔开。

样例

3 3
0 3 9
2 8 5
5 7 0

---

算法1

(dp) $O(n^2 m^2)$

C++ 代码

//来回传纸条和从起点传两次到终点是等价的，建模成从起点传两次到终点更好写
//dp[i][j][k][l]表示第一次传到(i,j)、第二次传到(k,l)时好心程度的最大值
//显然第一次传到(i,j)的最大值可以从(i-1,j)、(i,j-1)的最大值得来
//第二次传到(k,l)的最大值可以从(k-1,j)、(k,j-1)的最大值得来
//所以dp[i][j][k][l]的值是max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1],dp[i][j-1][k-1][l],dp[i][j-1][k][l-1])+a[i][j]+a[k][l];(两种转移方式的组合的最大值再加上两个格子上的值)
//需要注意的是i==k&&j==l时，此时两个纸条到了同一格子上，但是每个格子上的好心值只能计算一次，所以要减去重复的
//最后结果根据dp的定义是dp[n][m][n][m]
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 51;
int dp[N][N][N][N],a[N][N],m,n;
int main()
{
    cin >> n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            cin >> a[i][j];
    }
    for(int i=1;i<=n;i++)
    {
        for (int j = 1; j <=m; j ++ )
        {
            for(int k=1;k<=n;k++)
            {
                for(int l=1;l<=m;l++)
                {
                    dp[i][j][k][l]=max(dp[i-1][j][k-1][l],max(dp[i-1][j][k][l-1],max(dp[i][j-1][k-1][l],dp[i][j-1][k][l-1])))+a[i][j]+a[k][l];
                    if(i==k&&j==l)
                        dp[i][j][k][l]-=(a[i][j]+a[k][l]);
                }
            }
        }
    }
    cout << dp[n][m][n][m]<<endl;
    return 0;
}

Donate