DP问题 -- “传纸条”的解法
查看原帖
DP问题 -- “传纸条”的解法
1603098
J_Grigg楼主2024/12/2 14:48
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 200;

int f[N][N][N]; // f[k][i1][i2] : 分别走了k步,一个向右走了i1步(向下走了k-i1步),另一个同理
int w[N][N];

int main()
{
    int m, n;
    cin >> m >> n;
    for (int i = 1 ; i <= m ; i ++)
        for (int j = 1 ; j <= n ; j ++)
            cin >> w[i][j];
    
    for (int k = 1 ; k <= m + n ; k ++)
        for (int i1 = 1 ; i1 <= m ; i1 ++)
            for (int i2 = 1 ; i2 <= m ; i2 ++)
            {
                int j1 = k - i1, j2 = k - i2;
                if (j1 > 0 && j1 <= n && j2 > 0 && j2 <= n)
                {
                    int &x = f[k][i1][i2];
                    int t = w[i1][j1];
                    if (i1 != i2) t += w[i2][j2];
                    
                    x = max(x, f[k-1][i1][i2] + t);      //上一步都是向下走的
                    x = max(x, f[k-1][i1-1][i2] + t);    //上一步一个向右一个向下
                    x = max(x, f[k-1][i1][i2-1] + t);    //上一步一个向下一个向右
                    x = max(x, f[k-1][i1-1][i2-1] + t);  //上一步都向右走
                }

    cout << f[m + n][m][m] << endl;
    
    return 0;
}```
2024/12/2 14:48
加载中...