题目大意
思路
首先肯定要将数列排序，每部分一定是取连续的一段，于是就有了方程
$\Large f(i,j)=min(f(i-1,k-1)+(a_j-a_k)^2)$
其中$f(i,j)$表示前$j$个数分成$i$部分的最小值
解法一.四边形不等式优化
设$w(i,j)=(a_j-a_i)^2$
方程变为$f(i,j)=min(f(i-1,k-1)+w(k,j))$
很容易想到四边形不等式优化
证明w满足四边形不等式
$w(i,j)-w(i+1,j)=(a_j-a_i)^2-(a_j-a_{i+1})^2=a_i^2-a_{i+1}^2+2*a_j*(a_{i+1}-a_i)$
因为$a_{i+1}-a_i\ge 0$
所以$w(i,j)-w(i+1,j)$关于j单调不减，即$w(i,j)-w(i+1,j)\le w(i,j+1)-w(i+1,j+1)$
所以$w(i,j)+w(i+1,j+1)\le w(i,j+1)+w(i+1,j)$
以下证明具体可参考POJ1160 Post Office
证明f满足四边形不等式
设$f_k(i,j)=f(i-1,k-1)+w(k,j)$
对于$\forall i\le i^{'}\le j\le j^{'}$，设$k=s(i,j^{'}),t=s(i^{'},j)$
1.如果$k\le t$
有$f(i,j)+f(i^{'},j^{'})\le f(i-1,k-1)+w(k,j)+f(i^{'}-1,t-1)+w(t,j^{'})$
$f(i,j)+f(i^{'},j^{'})\le f(i-1,k-1)+w(k,j^{'})+f(i^{'}-1,t-1)+w(t,j)$
即$f(i,j)+f(i^{'},j^{'})\le f(i,j^{'})+f(i^{'},j)$
2.如果$k\gt t$
则只需证$f(i-1,t-1)+f(i^{'}-1,k-1)\le f(i-1,k-1)+f(i^{'}-1,t-1)$即可
设$k_1=s(i-1,k-1),k_2=s(i-2,k_1-1)……k_n=s(i-n,k_{n-1}-1)$
$t_1=s(i^{'}-1,t-1),t_2=s(i^{'}-2,t_1-1)……t_n=s(i^{'}-n,t_{n-1}-1)$
如果$k_1\le t_1$，就用1去证明
否则，递归2证明直到求证$f(1,t_n-1)+f(i_{'}-i+1,k_n-1)\le f(1,k_n-1)+f(i_{'}-i+1,t_n-1)$
化简得$w(1,t_n-1)+w(t_{n+1},k_n-1)\le w(1,k_n-1)+w(t_{n+1},t_n-1)$
因为w满足四边形不等式所以$f(i,j)+f(i^{'},j^{'})\le f(i,j^{'})+f(i^{'},j)$
证明$f(i,j)$的决策$s(i,j)$是单调的
1.设$k=s(i,j)$,对于所有$t\le k$
有$w(t,j)+w(k,j+1)\le w(t,j+1)+w(k,j)$
两边同时加上$f(i,t-1)+f(i,k-1)$得$f_t(i,j)+f_k(i,j+1)\le f_k(i,j)+f_t(i,j+1)$
因为$f_t(i,j)\ge f_k(i,j)$,所以$f_k(i,j+1)\le f_t(i,j+1)$
所以$s(i,j)\le s(i,j+1)$
2.设$k=s(i,j)$,对于所有$t\le k$
有$f(i,t-1)+f(i+1,k-1)\le f(i+1,t-1)+f(i,k-1)$
两边同时加上$w(t,j)+w(k,j)$得$f_t(i,j)+f_k(i+1,j\le f_k(i,j)+f_t(i+1,j)$
因为$f_t(i,j)\ge f_k(i,j)$,所以$f_k(i+1,j)\le f_t(i+1,j)$
所以$s(i,j)\le s(i+1,j)$
代码
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define maxn 10005
#define maxm 5005
int f[maxm][maxn],s[maxm][maxn],a[maxn];
void work(){
int n,m;scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)scanf("%d",a+i);
sort(a+,a+n+);
memset(f,0x3f,sizeof(f));
for(int i=;i<=n;i++)s[][i]=;
f[][]=;
for(int i=;i<=m;i++){
f[i][i]=;s[i][i]=i;s[i][n+]=n;
for(int j=n;j>i;j--){
for(int k=s[i-][j];k<=s[i][j+];k++){
if(f[i][j]>f[i-][k-]+(a[j]-a[k])*(a[j]-a[k])){
f[i][j]=f[i-][k-]+(a[j]-a[k])*(a[j]-a[k]);
s[i][j]=k;
}
}
}
}
printf("%d\n",f[m][n]);
}
int main(){
int t;scanf("%d",&t);
for(int i=;i<=t;i++)printf("Case %d: ",i),work();
return ;
}
解法二.斜率优化
若对于某个$f(i,j)$,$k$比$t$要优
那么$f(i-1,k-1)+(a_j-a_k)^2\le f(i-1,t-1)+(a_j-a_t)^2$
化简得$(f(i-1,k-1)+a_k^2-f(i-1,t-1)-a_t^2)/(2*(a_k-a_t))\le a_j$
然后就可以对每一个$i$分别用一次斜率优化$O(n)$得出$f$的值
可以用滚动数组优化空间
代码
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define maxn 10005
#define inf 0x3fffffff
int f[][maxn],a[maxn],que[maxn],s,t,k;
int calc(int k,int i,int j){
if(a[i]==a[j])return inf;
return (f[k][i-]+a[i]*a[i]-f[k][j-]-a[j]*a[j]-)/((a[i]-a[j])<<)+;//ÏòÉÏÈ¡Õû
}
void insert(int k,int x){
while(s<t-&&calc(k,x,que[t-])<=calc(k,que[t-],que[t-]))t--;
que[t++]=x;
}
void work(){
int n,m;scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)scanf("%d",a+i);
sort(a+,a+n+);
s=t=;que[t++]=;
for(int i=;i<=m;i++){
k=i&;f[k][i]=;
for(int j=i+;j<=n;j++){
while(s<t-&&calc(k^,que[s+],que[s])<=a[j])s++;
int x=que[s];
f[k][j]=f[k^][x-]+(a[j]-a[x])*(a[j]-a[x]);
}
s=t=;
for(int j=i+;j<=n;j++){
insert(k,j);
}
}
printf("%d\n",f[m&][n]);
}
int main(){
int t;scanf("%d",&t);
for(int i=;i<=t;i++)printf("Case %d: ",i),work();
return ;
}