P7872 「Wdoi-4」觉姐姐和恋妹妹 题解

· · 题解

由于小波的原 std 被叉爆了所以自己写个题解给大家谢罪了。/kt

首先对恋恋预处理出数组 f_{i,j} 代表从位置 (i,j) 走到她的终点能获得的最大愉悦程度。这里不用考虑觉的影响。

如果假设觉和恋在一起行动（这是经典 trick），那么可以设计 dp 状态。dp_{i,j,k} 代表觉和恋一起走了 i 步，觉有 j 步向左，恋有 k 步向左的最大愉悦程度。但这看起来很不可做。我们考察觉和恋的移动过程。如果觉和恋分开，那么觉会收集愉悦程度为正数的物品，并在她们相遇时把这些物品都给恋。如果觉和恋相遇，那么觉会带走愉悦程度为负数的物品，并把它们在两人不在同一格子时丢弃掉。

麻烦的地方在于，你不知道觉和恋之后会不会相遇/离开，而觉的行动是依赖于这个的。我的思路是不妨首先假设觉一定能把物品带给恋恋/把负数物品带走。然后在觉和恋切换状态（即，相遇变成分离，分离变成相遇）时对答案进行统计。也就是说假设这步后恋一个人走到终点不受觉的影响，然后和 ans 进行 \text{chkmax}。

注意特判一下，如果恋的终点可以到觉的终点，那么觉和恋都在恋的终点的这种状态也是合法的，和 ans 也要 \text{chkmax}。

附一份代码，大约拍了 600 组。有 hack 可以私我。

#include <bits/stdc++.h>
using namespace std;

int w[310][310];
long long dp[610][310][310];
long long f[310][310];
int e1_x, e1_y, e2_x, e2_y;

int satori_dis;
int koishi_dis;

bool chk(int xa, int ya, int xb, int yb){
    return xa <= e1_x && ya <= e1_y && xb <= e2_x && yb <= e2_y;
}

bool same(int xa, int ya, int xb, int yb){
    return xa == xb && ya == yb;
}

int main(){
//  freopen("1.in","r",stdin);
//    freopen("3.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++){
            cin >> w[i][j];
        }
    cin >> e1_x >> e1_y >> e2_x >> e2_y;
    satori_dis = e1_x + e1_y - 2;
    koishi_dis = e2_x + e2_y - 2;
    int cangt = 0;
    if (satori_dis > koishi_dis && e1_x >= e2_x && e1_y >= e2_y){
        cangt = 1;//shaber xiaobo fnfnfnfnfnfn
    }
    for (int i = 0; i <= n; i++) for (int j = 0; j <= m; j++) f[i][j] = LONG_LONG_MIN;
    for (int i = e2_x; i >= 1; i--){
        for (int j = e2_y; j >= 1; j--){
            if (i == e2_x){
                if (j == e2_y) f[i][j] = w[i][j];
                else f[i][j] = w[i][j] + f[i][j + 1];
            }
            else{
                if (j == e2_y) f[i][j] = w[i][j] + f[i + 1][j];
                else f[i][j] = w[i][j] + max(f[i][j + 1], f[i + 1][j]);
            }
        }
    }
    for (int i = 0; i <= n + m; i++)
        for (int j = 0; j <= n; j++)
            for (int k = 0; k <= n; k++){
                dp[i][j][k] = LONG_LONG_MIN;
            }
    dp[0][0][0] = max(0, w[1][1]);
    long long ans = f[1][1];
    for (int i = 0; i <= min(satori_dis, koishi_dis) - 1; i++){
        for (int j = 0; j <= min(i, e1_x - 1); j++)
            for (int k = 0; k <= min(i, e2_x - 1); k++){
                for (int p = 0; p <= 1; p++)
                    for (int q = 0; q <= 1; q++){
                        int nxa = 1 + j + p;
                        int nya = 1 + (i - j) + (1 - p);
                        int nxb = 1 + k + q;
                        int nyb = 1 + (i - k) + (1 - q);
                        if (!chk(nxa, nya, nxb, nyb)) continue;
                        int xa = 1 + j;
                        int ya = 1 + (i - j);
                        int xb = 1 + k;
                        int yb = 1 + (i - k);
                        if (same(xa, ya, xb, yb) != same(nxa, nya, nxb, nyb)){
                            ans = max(ans, dp[i][j][k] + f[nxb][nyb]);
                        }
                        if (same(nxa, nya, nxb, nyb)){
                            dp[i + 1][j + p][k + q] = max(dp[i + 1][j + p][k + q], dp[i][j][k] + max(0, w[nxa][nya]));
                        }
                        else{
                            dp[i + 1][j + p][k + q] = max(dp[i + 1][j + p][k + q], dp[i][j][k] + max(0, w[nxa][nya]) + w[nxb][nyb]);
                        }
                    }
            }
    }
    if (cangt){
        ans = max(ans, dp[koishi_dis][e2_x - 1][e2_x - 1]);
    }
    cout << ans << endl;
    return 0;
}