斜率优化DP，和玩具装箱很像。。。基本是裸的
注：那个Bf函数是暴力DP，可以参考一下和下面Upper函数(斜率优化DP)的共同点
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<queue>
using namespace std;
int first,last,Que[30005];
long long n,m,f[3005][3005],a[3005];
void Bf(){
for(int i=1;i<=n;i++){
f[i][1]=a[i]*a[i];
for(int j=2;j<=m;j++){
f[i][j]=f[i][j-1];
for(int k=1;k<i;k++){
f[i][j]=min(f[i][j],f[k][j-1]+(a[i]-a[k])*(a[i]-a[k]));
}
}
}
printf("%lld\n",m*f[n][m]-a[n]*a[n]);
}
bool DelFirst(int q1,int q2,int i,int j){
return f[q1][j-1]+a[q1]*a[q1]-2ll*a[q1]*a[i]>f[q2][j-1]+a[q2]*a[q2]-2ll*a[q2]*a[i];
}
bool DelLast(int q1,int q2,int i,int j){
return (f[q1][j-1]+a[q1]*a[q1]-f[q2][j-1]-a[q2]*a[q2])*(a[i]-a[q2])<(f[q2][j-1]+a[q2]*a[q2]-f[i][j-1]-a[i]*a[i])*(a[q2]-a[q1]);
}
void Upper(){
for(int i=1;i<=n;i++)f[i][1]=a[i]*a[i];
for(int j=2;j<=m;j++){
f[1][j]=a[1]*a[1];
first=1;
last=0;
Que[++last]=1;
for(int i=2;i<=n;i++){
while(first<last && DelFirst(Que[first],Que[first+1],i,j))first++;
f[i][j]=f[Que[first]][j-1]+(a[Que[first]]-a[i])*(a[Que[first]]-a[i]);
while(first<last && DelLast(Que[last-1],Que[last],i,j))last--;
Que[++last]=i;
}
}
printf("%lld\n",m*f[n][m]-a[n]*a[n]);
}
int main(){
freopen("4518.in","r",stdin);
freopen("4518.out","w",stdout);
scanf("%lld %lld",&n,&m);
for(int i=1;i<=n;i++){
long long x;
scanf("%lld",&x);
a[i]=a[i-1]+x;
}
Upper();
return 0;
}
评论 (0)
