「kuangbin带你飞」专题二十 斜率DP
layout: post 传送门 A.HDU - 3507 Print Article题意就是输出序列a[n],每连续输出的费用是连续输出的数字和的平方加上常数M 让我们求这个费用的最小值。 题解概率DP的入门题,把我搞得要死要活的。 首先dp[i]表示输出前i个的最小费用 很简单得得出一个方程 首先假设在算dp[i]的 ,k<j<i,并且J点比K点优秀 那么 另 所以我们另 2.如果 假设g[I,J]<sum[i] 就是I比J优秀,那么J就没存在的价值 相反,如果g[I,J]>sum[i] 那么同样有g[J,K]>sum[I] 那么K比J优秀 所以J是可以淘汰的 所以这样相当于维护一个下凸的图形,斜率在增加,用队列维护 ps:以上都是抄bin巨的博客 #include<bits/stdc++.h> using namespace std; typedef long long ll; #define pp pair<int,int> const ll mod=998244353; const int maxn=5e5+50; const ll inf=0x3f3f3f3f3f3f3f3fLL; int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;} int lcm(int a,int b){return a*b/gcd(a,b);} int dp[maxn]; int sum[maxn]; int a[maxn]; int q[maxn]; int m,n; int head,tail; int getDP(int i,int j){ return dp[j]+m+(sum[i]-sum[j])*(sum[i]-sum[j]); } int getUP(int j,int k){ return dp[j]+sum[j]*sum[j]-(dp[k]+sum[k]*sum[k]); } int getDOWN(int j,int k){ return 2*(sum[j]-sum[k]); } int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); while(cin>>n>>m){ for(int i=1;i<=n;i++)cin>>a[i]; memset(sum,sizeof(sum)); memset(dp,sizeof(dp)); for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i]; head=tail=0; q[tail++]=0; for(int i=1;i<=n;i++){ while(head+1<tail&&getUP(q[head+1],q[head])<=sum[i]*getDOWN(q[head+1],q[head])) head++; dp[i]=getDP(i,q[head]); while(head+1<tail&&getUP(i,q[tail-1])*getDOWN(q[tail-1],q[tail-2])<=getUP(q[tail-1],q[tail-2])*getDOWN(i,q[tail-1])) tail--; q[tail++]=i; } cout<<dp[n]<<endl; } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |