一個很顯然的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）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。