code1319 玩具装箱

一个划分dp，不过由于划分个数任意，仅用一维数组就可以

设dp[i]表示前i个装箱（任意个箱子）的费用最小值

dp[i]=min(dp[u]+cost(u+1,i))

但是n<=50000，n方的复杂度显然不能接受

设choice[i]数组存下对于每个i值，枚举所得的使f[i]最大的那个u值

打表，发现choice[]是单调不下降的

则每次对于一个新的i，在枚举u时只需要从choice[i-1]开始即可

代码：

#include<iostream>
#include<cstring>
#define Size 50005
using namespace std;

int n;
int c[Size];
long long sum[Size];
long long L;
long long dp[Size];
int choice[Size];

long long cost(int l,int r){
    long long x=sum[r]-sum[l-1] + r-l;
    return (x-L)*(x-L);
}

int main(){
    freopen("1319.in","r",stdin); 
    memset(dp,0x7f,sizeof(dp));
    
    cin>>n>>L;
    for(int i=1;i<=n;i++){
        cin>>c[i];
        sum[i]=sum[i-1]+c[i]; 
    }
    
    dp[0]=0;
    choice[0]=0; 
    for(int i=1;i<=n;i++){
        for(int u=choice[i-1];u<=i-1;u++){
            if(dp[u]+cost(u+1,i)<=dp[i]){
                dp[i]=dp[u]+cost(u+1,i);
                choice[i]=u;
            }
            
        }
    }
    
    cout<<dp[n]; 
    
    fclose(stdin); 
    return 0;
} 

为什么是单调的呢？请见 http://wenku.baidu.com/view/ef259400bed5b9f3f90f1c3a.html 

至于更好的O(n)的斜率优化，改天再说吧...sleeping