正題

題目鏈接:https://www.luogu.com.cn/problem/CF889E

---

題目大意

給出一個長度為$n$的序列$a$，定義函數$f(i,x)$有
$$f(n,x)=x\mathrm{m}\mathrm{o}\mathrm{d}{a}_n$$
$$f(i,x)=(x\mathrm{m}\mathrm{o}\mathrm{d}{a}_i)+f(x\mathrm{m}\mathrm{o}\mathrm{d}{a}_i)(i<n)$$
求最大的$f(1,x)$。
$1\le n\le 2\times 10^5,1\le a_i\le 10^{13}$

---

解題思路

考慮到最優解中我們肯定存在某次取模$a_i$后得到的是$a_i?1$，不然全部加$1$肯定更優。那么同樣的每個前綴的最優答案都滿足如下性質。

拿第一次來距離，就是說$[0,a_1)$中最優的是$a_1$，由于答案遞減，那么還沒有減去的值（目前的$x$）可能影響到后面的狀態，那么我們考慮維護$f_{i,j}$表示目前的$x=j$時已經被膜去的值貢獻為$f_{i,j}$，也就是答案目前為$i\times j+f_{i,j}$。

那么這個轉移來說我們就可以大膽地有$f_{i,j}=max\{f_{i,k}\}(k\ge j)$了，也就是開始時可以設$f_{i,a_1?1}=1$，會發現這樣來轉移的話最多只有$n$個有用的值（前綴最大）。

轉移的時候統計上減少的值對前面的貢獻即可，用一個$map$存下所有的有用位置和值進行轉移就好了，因為一個數字被模之后至少減少一半所以一個數字操作次數為$\log a_i$次。

時間復雜度：$O(n\log n\log a_i)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<map> #define ll long long using namespace std; const ll N=2e5+10; ll n,ans;map<ll,ll> f; map<ll,ll>::iterator it; signed main() {scanf("%lld",&n);for(ll i=1,x;i<=n;i++){scanf("%lld",&x);if(i==1)f[x-1]=0;else{for(it=f.lower_bound(x);it!=f.end();f.erase(it++)){ll j=(*it).first,w=(*it).second;f[j%x]=max(f[j%x],w+(i-1)*(j-j%x));f[x-1]=max(f[x-1],w+(i-1)*((j+1)/x*x-x));}}}for(it=f.begin();it!=f.end();it++)ans=max(ans,(*it).first*n+(*it).second);printf("%lld\n",ans);return 0; }

總結

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

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