本文共 2413 字，大约阅读时间需要 8 分钟。

为了解决这个问题，我们需要找到从矩阵的左上角(1,1)走到右下角(n,n)的两条路径，使得第一次路径经过的所有方格的值变为0。然后，第二条路径经过的方格的值之和最大。

方法思路

为了找到最优解，我们可以使用四维动态规划（DP）来解决这个问题。四维DP数组dp[i][j][k][t]表示第一个人从(1,1)走到(i,j)，第二个人从(1,1)走到(k,t)的最大值。状态转移方程考虑了从上方和左方来的路径，并确保在相同点上不重复计算值。

解决代码

#include 
   
    using namespace std;void read(T &x) {    T res = 0, f = 1;    char c = getchar();    while (!isdigit(c)) {        if (c == '-') f = -1;        c = getchar();    }    while (isdigit(c)) {        res = (res < 3) ? (res < 1 ? res * 10 + c - '0' : res * 10 + c - '0') : (res * 10 + c - '0') * 10 + c - '0';        c = getchar();    }    x = res * f;}void print(ll x) {    if (x < 0) {        putchar('-');        x = -x;    }    if (x > 9) print(x / 10);    putchar(x % 10 + '0');}const int maxn = 10;const ll mod = 1e9 + 7;ll n, mp[maxn][maxn];ll dp[maxn][maxn][maxn][maxn];ll gcd(ll a, ll b) {    return (b == 0) ? a : gcd(b, a % b);}ll qpow(ll a, ll p, ll mod) {    ll ans = 1;    a %= mod;    while (p) {        if (p & 1) ans = (ans * a) % mod;        a = (a * a) % mod;        p >>= 1;    }    return ans;}ll ksm(ll a, ll b) {    ll ret = 1;    while (b) {        if (b & 1) ret = (ret * a) % mod;        a = (a * a) % mod;        b >>= 1;    }    return ret;}int main() {    int T = 1;    while (T--) {        read(n);        while (scanf("%lld%lld%lld%lld", &x, &y, &k) != EOF) {            if (x == 0 && y == 0 && k == 0) break;            mp[x][y] = k;        }        for (ll i = 1; i <= n; ++i) {            for (ll j = 1; j <= n; ++j) {                for (ll k = 1; k <= n; ++k) {                    for (ll t = 1; t <= n; ++t) {                        ll option1 = dp[i-1][j][k-1][t];                        ll option2 = dp[i-1][j][k][t-1];                        ll option3 = dp[i][j-1][k-1][t];                        ll option4 = dp[i][j-1][k][t-1];                        ll max_opt = max(option1, option2, option3, option4);                        ll current_sum = max_opt + mp[i][j] + mp[k][t];                        if (i == k && j == t) {                            current_sum -= mp[i][j];                        }                        dp[i][j][k][t] = current_sum;                    }                }            }        }        cout << dp[n][n][n][n] << endl;    }}
   

代码解释

这个方法通过四维动态规划有效地解决了问题，确保了两条路径在相同点上不重复计算值，从而找到最优解。

转载地址：http://ihst.baihongyu.com/