【CF889E】Mod Mod Mod DP
DP mod
2023-09-11 14:15:24 时间
【CF889E】Mod Mod Mod
题意:给你一个序列$a_1,a_2...a_n$,定义$f(x,n)=x\mod a_n$,$f(x,i)=x\mod a_i+f(x \mod a_i,i+1) (1 \le i<n)$。
最大化f(x,1)。
$n\le 200000,a_i\le 10^9$
题解:超级神的DP题。(题目名字好暴力啊~)
首先有一个性质,一个数对一个比它小的数取模,最多取log次就会变成0。我们思考如何利用这个性质。
如果我们令f[x][i]就是题目中的f(x,i),那么每次i++的时候我们都要更新所有的dp值。不过我们可以将答案变成i*x+b的形式,那么f[d][i]就代表当x<=d时,最大的b值。这也就是说,我们dp维护的其实使若干条线段,我们要在斜率一定的时候,最大化截距。
思考如何转移,我们从f[d][i]可以转移到$f[d \mod a_i][i+1]$,也可以转移到$f[a_i-1][i+1]$(前提:ai<=d)。我们发现我们可以将所有$f[a_i-1][i+1]$合并,并且对于d<ai的状态,dp值并不改变,我们可以不理会这些状态。所以时间复杂度是多少呢?
上面已经说过了,一个数我们只在它被取模的时候更新状态,并且每次我们只新加入一个数ai-1,所以最终复杂度是$O(n\log n)$的。
当然,如果你像我一样比较懒用map维护dp值,需要再加一个log。
#include <cstdio> #include <cstring> #include <map> #include <algorithm> #include <iostream> using namespace std; const int maxn=200010; typedef long long ll; ll n,ans,v; map<ll,ll> f; map<ll,ll>::iterator it; inline ll rd() { ll ret=0,f=1; char gc=getchar(); while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();} while(gc>='0'&&gc<='9') ret=ret*10+(gc^'0'),gc=getchar(); return ret*f; } int main() { n=rd(); ll i,a,b; f[rd()-1]=0; for(i=2;i<=n;i++) { v=rd(); while(f.begin()!=f.end()) { it=f.end(),it--,a=(*it).first,b=(*it).second; if(a<v) break; f[v-1]=max(f[v-1],b+(i-1)*(a-a%v-v)); f[a%v]=max(f[a%v],b+(i-1)*(a-a%v)); f.erase(it); } } for(it=f.begin();it!=f.end();it++) ans=max(ans,n*((*it).first)+(*it).second); printf("%I64d",ans); return 0; }
相关文章
- 【区间DP】Zuma
- 【BZOJ1044】[HAOI2008]木棍分割 二分+DP
- 【BZOJ1827】[Usaco2010 Mar]gather 奶牛大集会 树形DP
- 1045 Favorite Color Stripe (30 分)【难度: 中 / 知识点: DP】
- LightOJ 1422 Halloween Costumes (区间DP)
- UVaLive 10859 Placing Lampposts (树形DP)
- HDU 3652 B-number (数位DP)
- UVa 1025 A Spy in the Metro (DP动态规划)
- Daimayuan #224. 距离和——树形DP
- 浅谈期望DP
- hdu 1158 Employment Planning (dp)
- 【bzoj2427】[HAOI2010]软件安装 Tarjan+树形背包dp
- 【bzoj3036】绿豆蛙的归宿 期望dp
- 【codevs1380】没有上司的舞会 树形dp
- 【bzoj1864】[ZJOI2006]三色二叉树 树形dp