决战黎明 题解

· · 题解

分析

正解策略：两条战线每条一个大棋子打掉（抵消或击败）尽可能多的敌方棋子，然后若干个 1 级棋子上来对拼消耗剩余的敌方棋子。

考虑问题的模式：每条战线必然是能先打到某个敌方棋子然后打不下去了，只能尽可能去对拼这个敌方棋子。

结论 1：如果已经打不掉这个敌方棋子，那么放若干个 1 级棋子一定最优。

证明是显然的，这个敌方棋子等级消耗的量为放我方棋子的个数，显然越多越好。

结论 2：如果 a 级和 b 级我方棋子某条战线上被先后连续放出，且 b > 1 ，那么两个棋子合并一定不劣。

如果棋子 b 没有将某个敌方棋子打掉，那么显然 b 为 1 级棋子更优。

如果棋子 b 将某个或某些棋子打掉了，那么显然 a+b 也能将那个或那些棋子打掉，且打完后剩下的棋子必然不少。

结论 3：如果能多打一个敌方棋子，就多打一个，而用这些我方棋子预算去拆分成若干个 1 级对拼消耗一定不优。

打掉这个棋子多花费的预算显然不超过这个棋子的等级，而对拼消耗显然是预算等于敌方棋子的被消耗等级，显然前者不劣。

所以，递推出打掉到每个敌方棋子的最小我方棋子等级，二分每个第一战线敌方棋子攻打位置情况下第二战线最多打到哪里，再计入剩下的我方棋子等级即可。

标程

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
int T, n;
long long m;
int l[3];
int g[3][N];
int dp[3][N];
long long f[3][N];
int main() {
    scanf("%d%d", &T, &n);
    for(int ti = 1; ti <= T; ti++) {
        scanf("%lld", &m);
        long long o = 0;
        for(int i = 1; i <= n; i++) {
            scanf("%d", &l[i]);
            for(int j = 1; j <= l[i]; j++) scanf("%d", &g[i][j]), o += g[i][j];
        }
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= l[i]; j++) {
                if(g[i][j - 1] + j - 2 == dp[i][j - 1]) dp[i][j] = max(dp[i][j - 1] + 1, g[i][j] + j - 1);
                else dp[i][j] = max(dp[i][j - 1], g[i][j] + j - 1);
                f[i][j] = f[i][j - 1] + g[i][j];
            }
        }
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= l[i]; j++) {
                if(dp[i][j] >= g[i][j] + j && j < l[i]) f[i][j]++;
            }
        }
        long long ans = 0;
        for(int j = 0; j <= l[1]; j++) {
            int lf, r, mid;
            if(dp[1][j] > m) break;
            lf = 0;
            r = l[2] + 1;
            while(lf + 1 < r) {
                mid = (lf + r) >> 1;
                if(dp[1][j] + dp[2][mid] <= m) lf = mid;
                else r = mid;
            }
            ans = max(m - dp[1][j] - dp[2][lf] + f[1][j] + f[2][lf], ans);
        }
        printf("%lld\n", max(0ll, o - ans));
    }
    return 0;
}