CF1129D Isolation（分块+DP）

一个很显然的DP方程式：f[i]=Σf[j]，其中j<i且在[j+1,i]中出现1次的数不超过k个

乍一看挺神仙的，只会O(n^2)，就是对于每个位置从后向前扫一遍，边扫边统计出现1次的数的个数。不难发现，同一个数第一次出现时cnt++，第二次出现时cnt--，后面没有变化这不是废话吗？！

于是可以考虑记录一个后缀和，s[i]表示cnt的大小，然后从当前位置开始从右向左第一次出现的值为1，第二次出现的值为-1，之后为0。修改记录lst数组表示该数上次的位置即可。然后每次走一步只对一个数产生影响，就是只对两段的s值产生影响，线段树显然不能够维护一段某个值出现的次数（实际可能能够用高级数据结构但我不会），于是可以采用暴力美学：分块！

对每一块打个标记delta[i]表示块i的变化量（整体增减才计入），cnt[i]表示位置i进行单独修改后的值，sum[i][j]表示第i个块为值为j的f值之和。暴力修改，复杂度O(n^1.5)，可以通过。

#include<bits/stdc++.h> using namespace std; const int N=1e5+7,mod=998244353; int n,m,B,a[N],pos[N],bel[N],lst[N],f[N],cnt[N],delta[440],ans[440],sum[440][N]; void update(int u,int v) {int t=bel[u];sum[t][cnt[u]]=(sum[t][cnt[u]]-f[u]+mod)%mod;if(cnt[u]+delta[t]<=m)ans[t]=(ans[t]-f[u]+mod)%mod;cnt[u]+=v;sum[t][cnt[u]]=(sum[t][cnt[u]]+f[u])%mod;if(cnt[u]+delta[t]<=m)ans[t]=(ans[t]+f[u])%mod; } void add(int u,int v,int w) {if(u>v)return;int p=bel[u],q=bel[v];if(p+1>=q){for(int i=u;i<=v;i++)update(i,w);return;}for(int i=u;bel[i]==p;i++)update(i,w);for(int i=v;bel[i]==q;i--)update(i,w);for(int i=p+1;i<q;i++){if(w>0)if(m-delta[i]>=0)ans[i]=(ans[i]-sum[i][m-delta[i]]+mod)%mod;delta[i]+=w;if(w<0)if(m-delta[i]>=0)ans[i]=(ans[i]+sum[i][m-delta[i]])%mod;} }int main() {scanf("%d%d",&n,&m);B=sqrt(n);bel[0]=1;for(int i=1;i<=n;i++)scanf("%d",&a[i]),bel[i]=i/B+1;f[0]=sum[1][0]=ans[1]=1;for(int i=1;i<=n;i++){lst[i]=pos[a[i]];add(lst[lst[i]],lst[i]-1,-1);add(lst[i],i-1,1);int j=i-1;for(int j=i-1;j>=0&&bel[i]==bel[j];j--)if(cnt[j]+delta[bel[i]]<=m)f[i]=(f[i]+f[j])%mod;for(int j=bel[i]-1;j;j--)f[i]=(f[i]+ans[j])%mod;sum[bel[i]][0]=(sum[bel[i]][0]+f[i])%mod;if(delta[bel[i]]<=m)ans[bel[i]]=(ans[bel[i]]+f[i])%mod;pos[a[i]]=i;}printf("%d",f[n]); }

　　

转载于:https://www.cnblogs.com/hfctf0210/p/10475116.html

总结

以上是生活随笔为你收集整理的CF1129D Isolation（分块+DP）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。