HDU 3480 Division

卡$long ~~long$的水题。
设$f[i][j]表示前i个数分成j份的最小费用$。很明显，这道题要用$sort$。
转移方程：$f[i][j]=min~~f[k][j-1]+a[k+1]*a[i]$
化成$y=kx+b$的形式：
$a[k+1]^2+f[k][j-1]=2a[i]*a[k+1]+f[i][j]-a[i]^2$
$~~~~~~~~~~~~~~~y~~~~~~~~~~~~~~~~~~~~~=~~~~k~~~~~~~~~~~~x~~~~+~~~~b~~$
代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=10010;
const int M=N>>1;
int f[N][M],t,n,m,a[N],j,q[N],l,r;
int y(int i){return a[i+1]*a[i+1]+f[i][j-1];}//用int，否则会T 
int x(int i){return a[i+1];}
bool pd(int a,int b,int c)
{
	return (y(b)-y(a))*(x(c)-(x(b)))<(y(c)-y(b))*(x(b)-x(a));
}
#define g getchar()
void qr(int &x)
{
	char c=g;x=0;
	while(!('0'<=c&&c<='9'))c=g;
	while('0'<=c&&c<='9')x=x*10+c-'0',c=g;
}
int main()
{
	qr(t);
	for(int c=1;c<=t;c++)
	{
		qr(n);qr(m); 
		for(int i=1;i<=n;i++)qr(a[i]);
		sort(a+1,a+n+1);
		for(int i=1;i<=n;i++)f[i][1]=(a[i]-a[1])*(a[i]-a[1]);
		for(j=2;j<=m;j++)
		{
			l=r=1;q[1]=j-1;
			for(int i=j,k;i<=n;i++)
			{
				while(l<r&&y(q[l+1])-y(q[l])<=2*a[i]*(x(q[l+1])-x(q[l])))l++;
				k=q[l];
				f[i][j]=f[k][j-1]+(a[i]-a[k+1])*(a[i]-a[k+1]);
				while(l<r&&!pd(q[r-1],q[r],i))r--;
				q[++r]=i;
			}
		}
		printf("Case %d: %d
",c,f[n][m]);
	}
	return 0;
}

滚动数组：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=10010;
const int M=N>>1;
int f[N][2],t,n,m,a[N],u,v,q[N],l,r;
int y(int i){return a[i+1]*a[i+1]+f[i][v];}//用int，否则会T 
int x(int i){return a[i+1];}
bool pd(int a,int b,int c)
{
	return (y(b)-y(a))*(x(c)-(x(b)))<(y(c)-y(b))*(x(b)-x(a));
}
#define g getchar()
void qr(int &x)
{
	char c=g;x=0;
	while(!('0'<=c&&c<='9'))c=g;
	while('0'<=c&&c<='9')x=x*10+c-'0',c=g;
}
int main()
{
	qr(t);
	for(int c=1;c<=t;c++)
	{
		qr(n);qr(m); 
		for(int i=1;i<=n;i++)qr(a[i]);
		sort(a+1,a+n+1);
		for(int i=1;i<=n;i++)f[i][0]=(a[i]-a[1])*(a[i]-a[1]);
		u=1;v=0;
		for(int j=2;j<=m;j++,swap(u,v))
		{
			l=r=1;q[1]=j-1;
			for(int i=j,k;i<=n;i++)
			{
				while(l<r&&y(q[l+1])-y(q[l])<=2*a[i]*(x(q[l+1])-x(q[l])))l++;
				k=q[l];
				f[i][u]=f[k][v]+(a[i]-a[k+1])*(a[i]-a[k+1]);
				while(l<r&&!pd(q[r-1],q[r],i))r--;
				q[++r]=i;
			}
		}
		printf("Case %d: %d
",c,f[n][v]);
	}
	return 0;
}