[DMOI-R1] 实验基地题解

NightTide · 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 把武器所释放的最大能量。

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

不妨分三种情况讨论：

上一秒二人一起用
上一秒只有小 A 用武器
上一秒只有小 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;
}

[DMOI-R1] 实验基地 题解

[DMOI] 官方题解

20pts

50pts

100pts

[DMOI-R1] 实验基地题解