方格取数

给一个2d矩阵, 里面有数字, 求取两个线上的数字,使得和最大, 只能往下和右走.

这个题我开始以为是greedy, 直接取一次, 再取一次就可以了, 然后感觉是不对的, 因为第一次走如果取了最大的值, 肯定会走过一些不是最大的值的路径, 而这些路径上的值是否就一定没有包含次大的值呢? 这个是不知道的. 所以要同时走才可以.

因为是同时, 相当于两个人在走A: (i1, j1),B: (i2,j2), 那么应该有 2*2四种情况. 所以应该是4维dp..然后看了讨论里,用的是压缩一维的方法, 即:

因为是n*n这么大的个子, 而且还只能往下往右走, 那么最多的步数就是2*n. 那么, 设k为当前步数, 就可以通过i找到j, 因为i+j=k, 比如极限情况下, 先走右到头然后下到头, 就是i=n, k=2*n, j = k-i = 2*n – n = n, 这样可以压缩一维, 四维变成三维

还有, 当计算数字的时候,如果两个人在同一格, 应该只取一次. 其他情况取各自格上的数.

#include <iostream>
#include <algorithm>
using namespace std;

int i,j,f;
const int N = 20; 
int m[N][N];
int dp[N*2][N][N];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n;
    cin >> n; 
    while (cin >> i >> j >> f, i||j||f)
    {
        m[i][j] = f;
    }
    for (int k = 2; k <= 2*n; k++)
    {
        for (int i1 = 1; i1 <= n; i1++)
        {
            for (int i2 = 1; i2 <= n; i2++)
            {
                int j1 = k - i1;
                int j2 = k - i2;
                if (i1 < 1 || i2 < 1 || i1 > n  || i2 > n || j1 < 1 || j2 < 1 || j1 > n || j2 > n)
                {
                    continue;
                }
                int c = 0;
                if (i1 == i2 && j1 == j2)
                { 
                    c = m[i1][j1];// only pick once
                }
                else
                {
                    c = m[i1][j1] + m[i2][j2];
                }
                dp[k][i1][i2] = max(dp[k][i1][i2], dp[k - 1][i1][i2] + c)  ;
                dp[k][i1][i2] = max(dp[k][i1][i2], dp[k - 1][i1 - 1][i2] + c);
                dp[k][i1][i2] = max(dp[k][i1][i2], dp[k - 1][i1][i2 - 1] + c);
                dp[k][i1][i2] = max(dp[k][i1][i2], dp[k - 1][i1 - 1][i2 - 1] + c);
            }
        }
    }
    cout << dp[2*n][n][n] << endl; 
    return 0;
}