http://acm.hdu.edu.cn/showproblem.php?pid=2829
这道题用四边形和斜率都可以
四边形很简单，不多说，直接套(chao)模板
//#define _TEST _TEST
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
/************************************************
Code By willinglive Blog:http://willinglive.cf
************************************************/
#define rep(i,l,r) for(int i=l,___t=(r);i<=___t;i++)
#define per(i,r,l) for(int i=r,___t=(l);i>=___t;i--)
#define MS(arr,x) memset(arr,x,sizeof(arr))
#define LL long long
#define INE(i,u,e) for(int i=head[u];~i;i=e[i].next)
inline const int getint()
{
int r=0,k=1;char c=getchar();
for(;c<'0'||c>'9';c=getchar())if(c=='-')k=-1;
for(;c>='0'&&c<='9';c=getchar())r=r*10+c-'0';
return k*r;
}
/////////////////////////////////////////////////
int n,m;
int a[1010],sum[1010];
LL dp[1010][1010],s[1010][1010],cost[1010][1010];
/////////////////////////////////////////////////
/////////////////////////////////////////////////
void input()
{
m++;
rep(i,1,n) a[i]=getint(),sum[i]=sum[i-1]+a[i];
}
void solve()
{
MS(dp,0x3f);
rep(i,1,n) rep(j,i,n) cost[i][j]=cost[i][j-1]+(sum[j-1]-sum[i-1])*a[j];
rep(i,0,m) dp[0][i]=0;
rep(i,1,n) dp[i][1]=cost[1][i],s[i][1]=0;
rep(j,1,m)
{
s[n+1][j]=n;
per(i,n,j)
{
rep(k,s[i][j-1],s[i+1][j])
{
if(dp[i][j]>dp[k][j-1]+cost[k+1][i])
{
s[i][j]=k;
dp[i][j]=dp[k][j-1]+cost[k+1][i];
}
}
}
}
LL ans=(((unsigned long long)0)-1)>>1;
rep(i,1,m) ans=min(ans,dp[n][i]);
cout<<ans<<endl;
}
/////////////////////////////////////////////////
int main()
{
#ifndef _TEST
freopen("std.in","r",stdin); freopen("1.out","w",stdout);
#endif
while(scanf("%d%d",&n,&m),n+m)
{
input();
solve();
}
return 0;
}
斜率，我的草稿：
dp[i][j]=min{dp[k][j-1]+cost[k+1][i]}
sum[i][j]^2=(a[i]+...+a[j])^2=sum2[i][j]+2cost[i][j]
cost[i][j]=(sum[i][j]^2-sum2[i][j])/2
dp[i][j]=min{dp[k][j-1]+(sum[k+1][i]^2-sum2[k+1][i])/2}
dp[i][j]=min{dp[k][j-1]+(s[i]^2-2*s[i]*s[k]+s[k]^2-s2[i]+s2[k])/2}
x<y,x比y优
dp[x][j-1]+(s[i]^2-2*s[i]*s[x]+s[x]^2-s2[i]+s2[x])/2<dp[y][j-1]+(s[i]^2-2*s[i]*s[y]+s[y]^2-s2[i]+s2[y])/2
dp[x][j-1]+(-2*s[i]*s[x]+s[x]^2+s2[x])/2<dp[y][j-1]+(-2*s[i]*s[y]+s[y]^2+s2[y])/2
dp[x][j-1]-s[i]*s[x]+s[x]^2/2+s2[x]/2<dp[y][j-1]-s[i]*s[y]+s[y]^2/2+s2[y]/2
s[i]<(dp[y][j-1]+s[y]^2/2+s2[y]/2-dp[x][j-1]-s[x]^2/2-s2[x]/2)/(s[y]-s[x])
s[i]<(dp[y][j-1]+s[y]^2/2+s2[y]/2) - dp[x][j-1]+s[x]^2/2+s2[x]/2)) / (s[y] - s[x])
Y[k]=dp[k][j-1]+s[k]^2/2+s2[k]/2
X[k]=s[k]
s[i]<(Y[y]-Y[x]) / (X[y]-X[x])
满足条件小的优
斜率还有一种方法：http://hi.baidu.com/adrnpduvzbjnpsr/item/0af88fb33b03a3fb62388eda
基本思想也是转化为前缀和
//#define _TEST _TEST
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
/************************************************
Code By willinglive Blog:http://willinglive.cf
************************************************/
#define rep(i,l,r) for(int i=l,___t=(r);i<=___t;i++)
#define per(i,r,l) for(int i=r,___t=(l);i>=___t;i--)
#define MS(arr,x) memset(arr,x,sizeof(arr))
#define LL long long
#define INE(i,u,e) for(int i=head[u];~i;i=e[i].next)
inline const int getint()
{
int r=0,k=1;char c=getchar();
for(;c<'0'||c>'9';c=getchar())if(c=='-')k=-1;
for(;c>='0'&&c<='9';c=getchar())r=r*10+c-'0';
return k*r;
}
/////////////////////////////////////////////////
int n,m;
int a[1001];
LL s[1001],s2[1001];
LL dp[1001][1001];
int q[1010],l,r,j;
/////////////////////////////////////////////////
inline LL sqr(LL x){return x*x;}
LL X(int k){return s[k];}
LL Y(int k){return dp[k][j-1]+(sqr(s[k])+s2[k])/2;}
double slope(int k,int j){return (double)(Y(k)-Y(j))/(X(k)-X(j));}
/////////////////////////////////////////////////
void input()
{
m++;
rep(i,1,n) a[i]=getint(),s[i]=s[i-1]+a[i],s2[i]=s2[i-1]+sqr(a[i]);
}
void solve()
{
rep(i,1,n) dp[i][1]=(sqr(s[i])-s2[i])/2;
for(j=2;j<=m;j++)
{
l=r=0;
rep(i,1,n)
{
while(l<r&&slope(q[l],q[l+1])<s[i])l++;
int k=q[l]; dp[i][j]=dp[k][j-1]+(sqr(s[i]-s[k])-(s2[i]-s2[k]))/2;
while(l<r&&slope(q[r],q[r-1])>slope(i,q[r]))r--;
q[++r]=i;
}
}
cout<<dp[n][m]<<endl;
}
/////////////////////////////////////////////////
int main()
{
#ifndef _TEST
freopen("std.in","r",stdin); freopen("2.out","w",stdout);
#endif
while(scanf("%d%d",&n,&m),n+m)
{
input();
solve();
}
return 0;
}