正題

CF889E
luogu

---

題目大意

給你 n 個數，讓你選擇一個X，使得 ${\sum }_{i=1}^{n}X\mathrm{m}\mathrm{o}\mathrm{d}{a}_1\mathrm{m}\mathrm{o}\mathrm{d}{a}_2...\mathrm{m}\mathrm{o}\mathrm{d}{a}_i$ 最大

---

解題思路

可以發現必定存在一個 i ，使得當前點貢獻為 $a_i$，否則把 X 加一顯然可以得到更優的答案

樸素的狀態轉移很難優化，考慮令 $f_{i,j}$ 表示到第 i 個點，當前值為 $0～j$，當前總貢獻為 $i\times (0～j)+f_{i,j}$，即把 j 個狀態存到了一起，然后把模后的貢獻存在 f 中

對于 $a_{i+1}>j$，直接傳遞即可

否則存在兩種轉移

$$\begin{gathered} f_{i+1,j\mathrm{m}\mathrm{o}\mathrm{d}{a}_{i+1}}=max(f_{i,j}+i\times (j?j\mathrm{m}\mathrm{o}\mathrm{d}{a}_{i+1}) \\ {f}_{i+1,a_{i+1}?1}=max(f_{i,j}+i\times (((j+1)/a_{i+1}\times a_{i+1}?1)?(a_{i+1}?1)) \end{gathered}$$

第二個轉移即找到最大的值使其轉移到 $a_{i+1}?1$

因為一個數模了之后至少減半，所以最多轉移 $logx$次

時間復雜度 $O(nlognlogx)$

---

code

#include<map> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; map<ll,ll>::iterator it; ll n,x,y,z,ans; map<ll,ll>f; int main() {scanf("%lld",&n);for(int i=1;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++)){y=(*it).first;z=(*it).second;f[y%x]=max(f[y%x],z+(i-1)*(y-y%x));f[x-1]=max(f[x-1],z+(i-1)*((y+1)/x*x-x));}}}for(it=f.begin();it!=f.end();it++)ans=max(ans,(*it).first*n+(*it).second);printf("%lld",ans);return 0; }

總結

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

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