正题
题目链接:https://www.luogu.com.cn/problem/CF889E
题目大意
给出一个长度为\(n\)的序列\(a\)，定义函数\(f(i,x)\)有
\[f(n,x)=x\bmod a_n
\]
\[f(i,x)=(x\bmod a_i)+f(x\bmod a_i)(i<n)
\]
求最大的\(f(1,x)\)。
\(1\leq n\leq 2\times 10^5,1\leq a_i\leq 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\geq 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;
}