题目大意：给定一个长度为n的序列，至多将序列分成m+1段，每段序列都有权值，权值为序列内两个数两两相乘之和。m<=n<=1000.
分析：令w[i,j]表示区间[i,j]中两两乘积之和,f[i][j]表示前j个数分成i段的最小值。
f[i][j]=f[i-1][k]+w[k+1,j]
w[k+1,j]可以转换为w[1,j]-w[1,k]-sum[k]*(sum[j]-sum[k])
其中sum[j]表示前j个数的前缀和。
f[i][j]=f[i-1][k]+w[j]-w[k]-sum[k]*(sum[j]-sum[k])
令y=f[i-1][k]+w[j]-w[k]+sum[k]^2,x=sum[k],b=sum[j],g=f[i][j],则有：
y-bx=g
此为直线方程，b为定值，要求g最小，即为直线的截距最小。平面上有若干点(x,y),这些点是由各个决策点产生的。而将直线从下往上平移，它接触到的第一个点即为最佳决策点。因为斜率b是上升的，所以，下一阶段的直线方程斜率更高，于是最佳决策点一定形成了下凸包序列。
#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXN 1005
#define LL long long int
LL f[MAXN][MAXN],w[MAXN],sum[MAXN];
#define FZ(i,p) (f[i-1][p]-w[p]+sum[p]*sum[p])
int n,m,num[MAXN];
int que[MAXN],head,tail;
#define MAXZ (1LL<<22)
bool turnup(int i,int p1,int p2,int p3) //p1>p2>p3
{
LL y1=FZ(i,p1);
LL x1=sum[p1];
LL y2=FZ(i,p2);
LL x2=sum[p2];
LL y3=FZ(i,p3);
LL x3=sum[p3];
if((x2-x3)*(y1-y2)>(x1-x2)*(y2-y3))return ;
else return ;
}
int main()
{
while(scanf("%d%d",&n,&m)&&(n||m))
{
memset(sum,,sizeof sum);
memset(w,,sizeof w);
m++;
for(int i=;i<=n;i++)
{scanf("%d",&num[i]);
sum[i]=sum[i-]+num[i];
w[i]=w[i-]+sum[i-]*num[i];
}
for(int i=;i<=n;i++)
f[][i]=w[i];
for(int i=;i<=m;i++)
{
//f[i-1][i-1]=0;
head=tail=;
que[tail++]=i-;
for(int j=i;j<=n;j++)
{
while(head<tail-&&FZ(i,que[head+])-FZ(i,que[head])<sum[j]*(sum[que[head+]]-sum[que[head]]))head++;
int k=que[head];
f[i][j]=f[i-][k]+w[j]-w[k]-sum[k]*(sum[j]-sum[k]);
while(head<tail-&&turnup(i,j,que[tail-],que[tail-])==)
tail--;
que[tail++]=j;
}
}
/*
for(int i=1;i<=m;i++)
{for(int j=1;j<=n;j++)
printf("%I64d ",f[i][j]);
printf("\n");
}
*/
printf("%I64d\n",f[m][n]);
}
}
本题也可以用平行四边形优化。
f[i][j]=f[i-1][k]+w[k+1,j]
w[k+1,j]很明显满足区间包含性质和平行四边形性质,所以f[i][j]也满足平行四边形性质，所以设s[i][j]表示f[i][j]的最佳决策点。s[i-1][j]<=s[i][j]<=s[i][j+1]。
从常识角度来思考，也是比较好想的。
如果数组元素不变，分段数增加，肯定分界点会往两边扩展，若分段数减少，则分界点会往中间靠拢，所以s[i][j]<=s[i+1][j]
如果分段数不变，数的个数增加（右边补充进来），分界点应该往右微调；如果数的个数减少（从右边剔除），分界点应该往左微调，所以有s[i][j-1]<=s[i][j]
所以s[i-1][j]<=s[i][j]<=s[i][j+1]
#include<iostream>
#include<cstring>
#include<cstdio>
#define MAXN 1005
#define MAXM 1005
#define LL long long int
#define min(a,b) ((a)<(b)?(a):(b))
LL f[MAXN][MAXM],sum[MAXN],w[MAXN],s[MAXN][MAXM];
int num[MAXN],t,n,m;
using namespace std;
void pre()
{
for(int i=;i<=n;i++)
sum[i]=sum[i-]+num[i];
for(int i=;i<=n;i++)
w[i]=w[i-]+sum[i-]*num[i];
}
int main()
{
while(scanf("%d%d",&n,&m)&&(n||m))
{
m++;
for(int i=;i<=n;i++)
scanf("%d",&num[i]);
memset(f,0x3f,sizeof f);
pre();
for(int i=;i<=n;i++)
{for(int j=i;j<=n;j++)
s[i][j]=i-;
}
for(int i=;i<=n;i++)
s[i][m+]=i-;
for(int i=;i<=n;i++)
f[i][i]=;
for(int j=;j<=n;j++)
f[j][]=w[j]; for(int i=;i<=n;i++)
for(int j=min(m,i);j>=;j--)
{
for(int k=s[i][j+];k>=s[i-][j];k--)
{
LL temp=f[k][j-]+w[i]-w[k]-sum[k]*(sum[i]-sum[k]);
if(f[i][j]>temp)
{f[i][j]=temp;
s[i][j]=k;
}
}
}
printf("%I64d\n",f[n][m]);
}
}