今天考试考了一个斜率优化DP，一大群人A了。。
这让从没写过斜率优化的我情何以堪
所以我就把这题写了。。
感觉还是很好理解的：维护最优决策，再维护决策单调性
顺便Orz lyz rky今天AK了省选模拟
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
int n,first,last;
long long L,s[50005],dp[50005],q[500005],C;
bool DelFirst(int a,int b,int c){
return dp[a]+(s[c]-s[a]-C)*(s[c]-s[a]-C)>dp[b]+(s[c]-s[b]-C)*(s[c]-s[b]-C);
}
bool DelLast(int a,int b,int c){
return (dp[a]-dp[b]+s[a]*s[a]-s[b]*s[b])*(s[c]-s[b])<(dp[b]-dp[c]+s[b]*s[b]-s[c]*s[c])*(s[b]-s[a]);
}
int main(){
freopen("1010.in","r",stdin);
freopen("1010.out","w",stdout);
scanf("%d %d",&n,&L);
C=L+1;
for(int i=1;i<=n;i++){
long long x;
scanf("%lld",&x);
s[i]=s[i-1]+x;
}
for(int i=1;i<=n;i++)s[i]+=i;
first=1;
last=0;
q[++last]=0;
for(int i=1;i<=n;i++){
while(first<last && DelFirst(q[first],q[first+1],i))first++;
dp[i]=dp[q[first]]+(s[i]-s[q[first]]-C)*(s[i]-s[q[first]]-C);
while(first<last && DelLast(q[last-1],q[last],i))last--;
q[++last]=i;
}
printf("%lld\n",dp[n]);
return 0;
}
评论 (0)
