https://codeforces.com/contest/1854/problem/B
看了官方题解才大概懂的。
先设想一个前提，如果要求你最后开了恰好x张牌，并且x<n，那么你获得的分数是多少？
很明显，那么是把前x张牌的分数全部拿到，然后去掉从一开始送的1张牌以外另外需要开的x-1张牌，因为每失去一分其实就可以多开一张牌，那么最后的答案是 a[1]+...a[x]-(x-1) ，注意这里是不管x是怎么拿来的，拿几个样例模拟一下就可以理解了。也就是如果最后贪心得到的开牌结果是x<n的话，分数一定是这样的。
那这里有个问题就是为什么x==n的时候不一样呢？因为有可能实际上浪费掉了多余的开牌机会，其实能开的牌是x>=n的，只是没有那么多牌开了，导致白白损失了开牌次数。
为了统一这一种情况，可以在牌堆后面补上若干个为值为0的虚拟的牌，和上面的问题等价。
那么问题就变成了，遍历x从[1, n]，看看哪个x是可以取得的？然后在可以取得的x里面求最大的a[1]+...a[x]-(x-1)，由于x可以遍历，那么a[1]+...a[x]-(x-1)的最大值只需要每次前缀和算一算就O(1)知道了，问题只剩下了哪个x是可以取得的？
这个问题其实是类似于一个背包问题，就是一开始有1个开牌机会，开牌了之后又会有新的开牌机会，而且每次开牌机会要强制用光（哪怕溢出了n也要用光），问这样操作下去能凑出的x有哪些。
设dp[i]表示只使用前i张牌换取了若干次开牌机会，能组成的开牌次数x组成的集合。注意如果牌的序号>i那么在这一轮迭代中他只能作为换分的而不能作为开牌的。而序号<=i的可以拿来开牌也可以拿来换分
显然dp[0]={1}，因为题目天然送一个开牌机会。
dp[1]={1,1+a[1]}，分别对应了“拿第1张牌换取分数”，和“拿第1张牌换取了a[1]次开牌机会后，总共开了1+a[1]张牌，并且后续的牌只拿来换分数而不开牌”
dp[2]={1,1+a[1],1+a[1]+a2}
这里可以看出来，若前一次第i-1轮循环中，能凑出某个x_{i-1}的开牌次数，并且这个开牌次数>=i，才能在这个基础上打开第i张牌，转移到x_{i_1}+a[i]。对于加起来<i的开牌次数，是不能转移到新的状态的，只能停留在原地不动。
以此循环到dp[n]，同时抛弃掉>2n的结果，因为单步a[i]的最大值是n，所以最差情况是原本开牌到n-1，然后增加了一个a[n-1]=n的开牌次数，得到2n-1的开牌次数，而如果已经得到了>=n的开牌次数，则完全没有理由再进行开牌。这里不能丢弃掉x>n的结果或者将其简单化为x==n，因为x溢出n的部分要表示浪费掉的开牌次数。
上面这个算法的复杂度是O(n^2)的，因为要循环n次检索每一张牌，对于每次转移来说要对集合里的所有数字都进行一次处理。
这里有另一个奇技淫巧就是看见n的数据范围是105而不是25的话，可能要考虑用bitset进行加速的做法。反正复杂度算出来不超过108或者109就行。
那这里的dp[i]表示一个集合，并且转移的规律是>=i的元素x全部可以转移到x+a[i]。但小于的部分要维持原状。
如果用一个位向量来表示这个集合。bitset[x]=0表示不能组合出x，bitset[x]=1表示可以组合出x。那么这里相当于是：
bitset = (((oldbitset >> i) << a[i]) << i) | oldbitset
或者
bitset |= ((oldbitset >> i) << i) << a[i]
这里先右移i位，去掉[0, i-1]这些不能组合出超过i的值，然后让其他值归位（相当于把末i位清0），然后把这些能组合出x的统统变成能组合出x+a[i]，然后或上原向量表示不进行用第i张牌换次数的操作。
int n;
int a[200005];
ll prefix[200005];
ll dp[200005];
void solve() {
RD (n);
RDN (a, n);
for (int i = n + 1; i <= 2 * n; ++i) {
a[i] = 0;
}
for (int i = 1; i <= 2 * n; ++i) {
prefix[i] = prefix[i - 1] + a[i];
}
bitset<200005> dp = 0;
dp[1] = 1;
for (int i = 1; i <= n; ++i) {
dp |= ( ( (dp >> i) << i) << a[i]);
}
ll ans = 0;
for (int x = 1; x <= 2 * n; ++x) {
if (dp[x] == 0) {
continue;
}
ll tmp = prefix[x] - (x - 1);
cmax (ans, tmp);
}
WT (ans);
}