CF1322D Reality Show
Description
有 (n) 个元素，每个元素的大小为 (l_i) ，选择这个选手花费 (s_i) 的代价，大小为 (i) 的元素对应 (c_i) 的收益。依次将 (n) 个选手加入集合中，得到权值如下：
- 加入元素 (i) 时，立刻获得收益 (c_{l_i});
- 如果此时场上有大小相同的元素，将它们合并为一个大小等于这两个元素大小 (+1) 的数，获得新数对应的收益。重复此操作直到没有大小相同的元素。
求一个 (l_i) 单调不升的元素序列，将它们依次加入集合中，最大化其收益减去代价的值 （一个也不选也是合法的）。
(n,mle 2000,s_ile 5000,|c_i|le 5000)。
Solution
考虑朴素 (DP)，定义 (dp_{i,s}) 表示上一个选择的元素的大小为 (i)，目前集合中的元素为 (s) 时的最大收益，然后暴力枚举新加入的数的贡献来判断。
状态数实在太大了，考虑新加入的数加入后对状态的影响，可以发现它的贡献要么是连续合并许多个 (1) 直到遇到 (0)，要么就只会影响最后 (log n) 个数。前者的贡献难以计算，但我们可以将整个过程倒过来，在倒着的元素序列上找一个单调不减的元素序列，加入集合中，那么此时不会影响总答案，且不会再产生前一种贡献。
这是我们就只用维护最后 (log n) 的数的状态即可，总状态数为 (mathcal O(2^{log n})=mathcal O(n))。转移时，考虑当前元素的贡献可以 (mathcal O(log n)) 暴力判断。因此总复杂度为 (mathcal O(n^2log n))。
Code
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=2060;
int n,m,l[N],a[N],c[N<<1],dp[N][N],sum[N<<1],mx[N],trans[N][12];
int f[N][N],sf[N][N],k;
struct BIT{
int c[N];
inline int lowbit(int x){return x&(-x);}
inline void init(){memset(c+1,-0x3f,sizeof(int)*(m+1));}
inline void add(int x,int v){
x++;
for(;x<=m+1;x+=lowbit(x)) c[x]=max(c[x],v);
}
inline int query(int x){
x++;
int ret=-inf;
for(;x;x-=lowbit(x)) ret=max(ret,c[x]);
return ret;
}
}T[N];
int main(){
// freopen("test.in","r",stdin);
// freopen("talent.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",&l[i]);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i<=n+m;++i) scanf("%d",&c[i]);
for(int i=1;i<=n+m+1;++i) sum[i]=sum[i-1]+c[i];
l[n+1]=-n;
k=1;while((1<<k)<=max(n,m)) ++k;
const int M=(1<<k)-1;
memset(dp,-0x3f,sizeof(dp));
memset(f,-0x3f,sizeof(f));
dp[n+1][1]=0;
f[0][1]=0;
for(int i=0;i<=M;++i) T[i].init();
T[1].add(0,0);
int ans=0;
for(int s=0;s<M;++s){
for(int i=0;i<=k;++i) if((s>>i)&1){mx[s]=i;break;}
for(int i=0;i<=k;++i) trans[s][i]=((s>>i)+1)&M;
}
for(int i=n;i>=1;--i){
for(int t=l[i];t>=0;--t){
bool flag=(t==l[i]-k);if(!t) flag=true;
int tp=flag?k:l[i]-t;
for(int s=0;s<=M;++s){
int tmp=trans[s][tp];
int ff=(flag?T[s].query(t):f[t][s])-a[i]+sum[l[i]+mx[tmp]]-sum[l[i]-1];
dp[i][tmp]=max(dp[i][tmp],ff);
}
if(flag) break;
}
for(int s=0;s<=M;++s){
ans=max(ans,dp[i][s]);
f[l[i]][s]=max(f[l[i]][s],dp[i][s]);
T[s].add(l[i],dp[i][s]);
}
}
printf("%d
",ans);
return 0;
}