自动搬运

查看原文

来自洛谷，原作者为

	NightTide 我回来了

搬运于2025-08-24 22:43:26，当前版本为作者最后更新于2022-11-26 21:03:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[DMOI] 官方题解

20pts

首先能够发现性质，由于 $A,B,C,D$ 均为正数，所以一定不可能出现某一个时刻两个人都没有使用武器的情况。

然后开始打爆搜，每个时刻有三种情况，同时记录下每个人距离上次使用武器的时间。

时间复杂度 $O(3^{n + m})$，期望得分 20pts。

50pts

根据上面说的性质我们能够发现，总时间不会超过 $n + m$。考虑用动态规划：

设 $dp_{i,j,k}$ 表示在时刻 $i$，小 $A$ 用了 $j$ 把武器，小 $B$ 用了 $k$ 把武器所释放的最大能量。

根据上面说的性质，上一秒一定有至少一个人用了武器。

不妨分三种情况讨论：

1. 上一秒二人一起用
2. 上一秒只有小 $A$ 用武器
3. 上一秒只有小 $B$ 用武器

第一种情况直接转移，后两种情况枚举另一个人上一次使用武器的时间进行转移，时间复杂度 $O(n^4)$。

发现可以使用单调栈辅助转移，转移优化到 $O(1)$，时间复杂度优化到 $O(n^3)$，期望得分 50pts。

100pts

由于吸收的能量与休息时间成一次函数关系，时间一维其实可以薅掉。

设 $dp_{i,j,0/1,0/1}$ 表示小 $A$ 用了 $i$ 把武器，小 $B$ 用了 $j$ 把武器。后面两维分别表示当前时刻小 $A$ 是 $/$ 否使用了武器，当前时刻小 $B$ 是 $/$ 否使用了武器。

其他的贡献的计算都很简单，主要是能量吸收量的计算。以小 $A$ 为例。

先考虑 $B = 0$ 的情况。

若小 $A$ 当前时刻没有使用武器。小 $A$ 的休息时间相当于多了 $1$ 个单位时间，那么他就会再吸收 $A$ 的能量。

直接在转移的时候减去 $A$ 就好。

但是 $B \not= 0$ 怎么办？

发现加吸收 $B$ 的能量的次数与休息的次数是一致的，我们在转移的时候可以钦定一个规则：当上一时刻使用了武器，但是当前时刻没有使用武器，那么小 $A$ 的休息次数就会加 $1$，此时就减去 $B$。

具体实现参见代码：

#include<bits/stdc++.h>
#define MAXN 3001
#define INF 0x3f3f3f3f
using namespace std;
int n, m, A, B, C, D;
int a[MAXN], b[MAXN], d[MAXN][MAXN];
int dp[MAXN][MAXN][2][2];
inline int read(){
   int s = 0, w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar(); }
   while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
   return s * w;
}
int main(){
    // freopen("data.in", "r", stdin);
    // freopen("std.txt", "w", stdout);
    n = read(); m = read();
    for(int i = 1; i <= n; i++) a[i] = read(); //scanf("%d",&a[i]);
    for(int i = 1; i <= m; i++) b[i] = read(); //scanf("%d",&b[i]);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            // scanf("%d",&d[i][j]);
            d[i][j] = read();
        }
    }
    scanf("%d%d%d%d",&A,&B,&C,&D);
    memset(dp, -0x3f, sizeof(dp));
    dp[1][0][1][0] = a[1] - C - D;
    dp[0][1][0][1] = b[1] - A - B;
    dp[1][1][1][1] = a[1] + b[1] + d[1][1];
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= m; j++){
            if(i != 0){
                // dp[i][j][1][0];
                dp[i + 1][j][1][0] = max(dp[i + 1][j][1][0], dp[i][j][1][0] + a[i + 1] - C);
                dp[i][j + 1][0][1] = max(dp[i][j + 1][0][1], dp[i][j][1][0] + b[j + 1] - A - B);
                dp[i + 1][j + 1][1][1] = max(dp[i + 1][j + 1][1][1], dp[i][j][1][0] + a[i + 1] + b[j + 1] + d[i + 1][j + 1]);
            }
            if(j != 0){
                // dp[i][j][0][1];
                dp[i + 1][j][1][0] = max(dp[i + 1][j][1][0], dp[i][j][0][1] + a[i + 1] - C - D);
                dp[i][j + 1][0][1] = max(dp[i][j + 1][0][1], dp[i][j][0][1] + b[j + 1] - A);
                dp[i + 1][j + 1][1][1] = max(dp[i + 1][j + 1][1][1], dp[i][j][0][1] + a[i + 1] + b[j + 1] + d[i + 1][j + 1]);
            }
            if(i != 0 && j != 0){
                // dp[i][j][1][1];
                dp[i + 1][j][1][0] = max(dp[i + 1][j][1][0], dp[i][j][1][1] + a[i + 1] - C - D);
                dp[i][j + 1][0][1] = max(dp[i][j + 1][0][1], dp[i][j][1][1] + b[j + 1] - A - B);
                dp[i + 1][j + 1][1][1] = max(dp[i + 1][j + 1][1][1], dp[i][j][1][1] + a[i + 1] + b[j + 1] + d[i + 1][j + 1]);
            }
        }
    }
    int ans = -INF;
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= m; j++){
            ans = max(ans, dp[i][j][1][0]);
            ans = max(ans, dp[i][j][0][1]);
            ans = max(ans, dp[i][j][1][1]);
        }
    }
    printf("%d\n",ans);
    return 0;
}