AcWing 1027. 方格取数（高难度线性dp）

╰半夏微凉° 2022-08-28 11:49 232阅读 0赞

本来想着先用dp获取最大值，然后标记，最后再dp一遍，貌似可以实现。

正解：两条路线每次走的步数是一样的，k = i1 + j1 = i2 + j2

比较来自四个方位的点的大小

引用的目的是为了让 dp 随之改变

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int v[15][15];
int dp[50][15][15];
int main()
{ 
    int n, a, b, c;
    cin >> n;
    while (cin >> a >> b >> c and a|b|c) v[a][b] = c;
    for(int k = 2; k <= n + n; k++)
    { 
        for(int i1 = 1; i1 <= n; i1++)
        { 
            for(int i2 = 1; i2 <= n; i2++)
            { 
                int j1 = k-i1, j2 = k - i2;
                if(j1 <= n and j1 >= 1 and j2 <= n and j2 >= 1)
                { 
                    int &x = dp[k][i1][i2];
                    int t = v[i1][j1];
                    if(i1!=i2) t += v[i2][j2];
                    x = max(x, dp[k-1][i1-1][i2-1] + t);
                    x = max(x, dp[k-1][i1-1][i2] + t);
                    x = max(x, dp[k-1][i1][i2-1] + t);
                    x = max(x, dp[k-1][i1][i2] + t);
                }
            }
        }
    }
    cout << dp[n+n][n][n];
    return 0;
}