自动搬运

查看原文

来自洛谷，原作者为

	船酱魔王 如花美眷，似水流年

搬运于2025-08-24 23:15:15，当前版本为作者最后更新于2024-07-12 11:20:20，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

分析

正解策略：两条战线每条一个大棋子打掉（抵消或击败）尽可能多的敌方棋子，然后若干个 $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;
}