正題

題目鏈接:http://codeforces.com/contest/1603/problem/C

---

題目大意

定義一個序列$a$的$f(a)$為你每次可以將序列中的一個數$z$分裂成$x+y=z$，然后再把$x,y$放回原來的位置，然后$f(a)$表示把$a$變成不降序列的最少操作次數
給出一個長度為$n$的序列$a$，求它所有子區間的$f$值的和。

$1\le n,a_i\le 10^5$

---

解題思路

顯然的每個數字$a_i$最終肯定是分解為$k?1$個$?\frac{a_i}{k}?$和一個$?\frac{a_i}{k}?$。
然后我們對于一個序列可以從右往左每個選擇能分解的最小的次數來分肯定是最優的。
那么考慮暴力的$dp$，設$f_{i,j}$表示現在第$i$個，所有左端點為$i$的區間中$a_i$分解的最前面那個為$k$的方案，然后倒著轉移就好了。
考慮到$j$肯定是某個$?\frac{a_i}{k}?$，而$?\frac{a_i}{k}?$最多只有$2{\sqrt{a}}_i$種取值，所以我們可以只枚舉這些取值就好了。

時間復雜度：$O(n{\sqrt{a}}_i)$，略微卡常

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=1e5+10,P=998244353; ll T,n,ans,a[N],f[2][N],g[2][N]; signed main() {scanf("%lld",&T);while(T--){scanf("%lld",&n);for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);ll o=0;g[o][a[n]]=1;ans=0;for(ll i=n-1;i>=1;i--){o^=1;ll m=a[i+1];for(ll l=1,r;l<=m;l=r+1){r=m/(m/l);ll x=m/l,w=(a[i]+x-1)/x,k=a[i]/w;f[o][k]+=f[!o][x]+(w-1)*g[!o][x];g[o][k]+=g[!o][x];ans+=f[!o][x];ans%=P;f[!o][x]=g[!o][x]=0;}g[o][a[i]]++;}for(ll l=1,r;l<=a[1];l=r+1)r=a[1]/(a[1]/l),(ans+=f[o][a[1]/l])%=P,f[o][a[1]/l]=g[o][a[1]/l]=0;printf("%lld\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的CF1603C-Extreme Extension【整除分块,dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

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