【题解】CF1854B Earn or Unlock

你考虑，我们很容易地可以构造一个 \(n^2\) 的 DP：

• \(f_{i,j}\) 表示当前在 \(i\) 张牌，还可以摸 \(j\) 张牌的最大分数。转移也很好转移，你考虑一眼就会。

但是我们显然要缩减复杂度，我们看到数据范围 \(10^5\)，想到了根号。

分块？？？显然不行。莫队？？？都没有区间查询，怎么行呢？

然后你苦思冥想，到最后也没有想出来这道题。

你考虑其实我们可以把 \(j\) 这一维吃掉，如果我们将继续往下摸牌少去的牌的代价均摊到后面的 \(a_i\) 张牌上，那么我们知道一个 \(i\)，即可求出在该点的分数。

即对于位置 \(i\)，对应的分数为 \(\sum\limits_{j = 1}^n a_j - i + 1\)。

然后现在我们的要求就变成了看到底能不能在位置 \(i\) 摸到完最后一张牌。

我们可以发现这个转移是 \(n^2\) 的，但是因为状态只有 \(0/1\) 所以说可以使用 bitset 进行优化，让复杂度变为 \(O(\frac {n^2} \omega)\)

处理的时候还有一个细节，就是计算的时候，摸牌的最后一个位置可能会到达 \(2\times n\)，我们只需要将 \(a_{n+1\sim2n}\) 都赋值为 \(0\) 即可。

code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll NN = 2e5 + 8;
ll n,m,ans;
ll a[NN],pre[NN];
bool f[NN];
bitset<NN> dp;
int main(){
	scanf("%lld",&n);
	pre[0] = 0;dp[1] = 1;
	for(int i = 1; i <= n; ++i)
		scanf("%lld",&a[i]), pre[i] = pre[i-1] + a[i];
	for(int i = 1; i <= n; ++i){
		dp = (dp | (dp << a[i]));
		f[i] = dp[i];dp[i] = 0;
	}
	for(int i = n + 1; i <= 2 * n; ++i) {
		f[i] = dp[i];
		pre[i] = pre[i - 1];
	}
	ans = 0;
	for(int i = 1; i <= 2 * n; ++i) if(f[i]) ans = max(ans, pre[i] - i + 1);
	printf("%lld", ans);
	return 0;
}