斜率优化DP

简单的斜率优化模板题

1.BZOJ 1010 玩具装箱

  f[i]=f[j]+(i-j-1+sum[i]-sum[j]-L)^2;

  设a[i]=sum[i]+i, C=-1-L;

  f[i]=f[j]+(a[i]-a[j]+C)^2;

 考虑当j优于k时，有 

  f[j]+(a[i]-a[j]+C)^2<f[k]+(a[i]-a[k]+C)^2;

  展开 f[j]-2*a[i]*a[j]+a[j]^2-a*a[j]*C<f[k]+2*a[i]*a[k]+a[k]^2+2*a[k]*C;

设D=a[i]

   f[i]-f[k]+a[j]^2-a[k]^2<2*(D+C)*(a[j]-a[k])

   (f[j]+a[j]^2)-(f[k]+a[k]^2)/(a[j]-a[k])<2*(D+C);

  根据下图可知，当l(kj)<2*(D+C)时，k优于j,弹出j，当l（kj）>2*(D+C)时，j优于k，i优于j，弹出j

//Twenty
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int maxn=50000+299;
typedef long long LL;
LL sum[maxn],L,f[maxn];
int n,que[maxn],ql=1,qr=1;
double x(int i) {return sum[i]+i;}
double y(int i) {return f[i]+x(i)*x(i);}
int c(int i) {return 2*(sum[i]+i-L);}
double xl(int i,int j) {return (y(j)-y(i))/(x(j)-x(i));}
LL pf(int i) {return (LL)i*i;}
int main()
{
    scanf("%d%lld",&n,&L); L++;
    for(int i=1;i<=n;i++){
    scanf("%lld",&sum[i]);
    sum[i]+=sum[i-1];
    }
    for(int i=1;i<=n;i++){
        while(ql<qr&&xl(que[ql],que[ql+1])<=c(i)) ql++;
        int j=que[ql];
        f[i]=f[j]+pf(sum[i]+i-sum[j]-j-L);
        while(ql<qr&&xl(que[qr],i)<xl(que[qr-1],que[qr])) qr--;
        que[++qr]=i;
    }
    printf("%lld
",f[n]);
    return 0;
}

 

2.特别行动队

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1000000+29; 
typedef long long ll;
ll s[maxn],a,b,c,f[maxn];
int l,r,n,que[maxn];
ll x(int j){return f[j]+a*s[j]*s[j];}
ll y(int j){return s[j];}
ll C(int i){return a*s[i]*s[i]+b*s[i]+c;}
double xl(int j,int k) {return double(x(j)-x(k))/double(y(j)-y(k));}
ll inline read(){
    char ch=getchar();
    ll ret=0;
    while(ch<'0'||ch>'9') ch=getchar();
    for(;ch>='0'&&ch<='9';ch=getchar()) ret=ret*10+ch-'0';
    return ret;
}
int main()
{
    scanf("%d%lld%lld%lld",&n,&a,&b,&c);
    for(int i=1;i<=n;i++)
    s[i]=s[i-1]+read();
    l=r=1;que[1]=0;
    for(int i=1;i<=n;i++){
        while(l<r&&xl(que[l+1],que[l])>=b+2*a*s[i]) l++;
        int j=que[l];
        f[i]=f[j]-2*a*s[i]*s[j]+a*s[j]*s[j]-b*s[j]+C(i);
        while(l<r&&xl(que[r],que[r-1])<xl(i,que[r]))r--;
        que[++r]=i;
    }
    printf("%lld
",f[n]);
    return 0;
}