【BZOJ1010】玩具装箱

  这是一道斜率优化题。

  为了简化式子用sum[i]=c[1]+c[2]+...+c[i]，t[i]=sum[i]+i,m[i]=t[i]^2+f[i]，p[i]=2*(t[i]-L-1)

  设f[i]表示装入1..i这些玩具所需的最小费用，容易得到:

    f[i]=min{f[j]+(sum[i]-sum[j]+i-j-1-L)^2}(0<=j<i)

  对于两个决策j,k(j>k)，设它们对当前状态i的贡献分别为g(j),g(k)

  g(j)=f[j]+(t[i]-t[j]-L-1)^2   g(k)=f[k]+(t[i]-t[k]-L-1)^2

  g(j)-g(k)=(t[j]^2+f[j]-2*(t[i]-L-1)*t[j])  -  (t[k]^2+f[k]-2*(t[i]-L-1]*t[k])

        =(m[j]-p[i]*t[j])-(m[k]-p[i]*t[k])

  因为t[i]=sum[i]+i是递增的，所以t[j]>t[k]，可以得到当p[i]>(m[j]-m[k])/(t[j]-t[k])时g(j)<g(k)，即此时决策j更优

  接下来就是标准的斜率优化环节了。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
using namespace std;
const int maxn=50010;
const double eps=1e-8;
inline void read(int &x) {char ch;while ((ch=getchar())<'0' || ch>'9');x=ch-'0';while ((ch=getchar())<='9' && ch>='0') x=x*10+ch-'0';}
 
LL t[maxn],m[maxn],f[maxn];
int id[maxn];
int c[maxn];
int n,l;
 
double slope(const LL t1,const LL m1,const LL t2,const LL m2) {return (double)(m2-m1)/(t2-t1);}
 
void Init()
{
    read(n),read(l);
    LL sum=0;
    for (int i=1;i<=n;i++) read(c[i]);
}
 
void DP()
{
    LL sum=0;
    int head=1,tail=1;
    t[1]=m[1]=id[1]=0;
    for (int i=1;i<=n;i++)
    {
        sum+=c[i];
        LL ti=sum+i,pi=2*(ti-l-1),mi=ti*ti;
        while (tail-head && pi>slope(t[head],m[head],t[head+1],m[head+1])) head++;
        f[i]=f[id[head]]+(l+1+t[head]-ti)*(l+1+t[head]-ti);
        mi+=f[i];
        while (tail-head && slope(ti,mi,t[tail],m[tail])<slope(t[tail],m[tail],t[tail-1],m[tail-1])+eps) tail--;
        tail++;
        id[tail]=i;t[tail]=ti;m[tail]=mi;
    }
}
 
int main()
{
    Init();
    DP();
    printf("%lld\n",f[n]);
    return 0;
}

        太长时间没写过忘了，这里重新写了一个。更新于2017.11.30。

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;

double slope(long long a1,long long b1,long long a2,long long b2)
{
	return (double)(a1-a2)/(b1-b2);
}

long long a[maxn],b[maxn],sum[maxn];
long long f[maxn];
int c[maxn];
int n,L;

int q[maxn];
void DP()
{
	f[0]=0;
	a[0]=1;
	b[0]=2;
	int top=1,tail=1;
	for (int i=1;i<=n;i++)
	{
		long long t=i+sum[i]-L;
		while (top<tail && a[q[top]]-t*b[q[top]]>=a[q[top+1]]-t*b[q[top+1]]) top++;
		f[i]=a[q[top]]-t*b[q[top]]+t*t;
		a[i]=f[i]+(i+1+sum[i])*(i+1+sum[i]);
		b[i]=2*(i+1+sum[i]);
		//while (top<tail && slope(a[i],b[i],a[q[tail]],b[q[tail]])<slope(a[q[tail]],b[q[tail]],a[q[tail-1]],b[q[tail-1]])) tail--;
		while (top<tail && (a[i]-a[q[tail]])*(b[q[tail]]-b[q[tail-1]])<(b[i]-b[q[tail]])*(a[q[tail]]-a[q[tail-1]])) tail--;
		q[++tail]=i;
	}
}

int main()
{
	scanf("%d%d",&n,&L);
	for (int i=1;i<=n;i++) scanf("%d",&c[i]),sum[i]=sum[i-1]+c[i];
	DP();
	printf("%lld\n",f[n]);
	return 0;
}