斜率dp
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define maxn 10005 #define maxm 5005 using namespace std; int dp[maxn][maxm]; int q[maxn*10]; int num[maxn]; bool check(int j,int tail,int i) { int yk=dp[q[tail-1]][j-1]+num[q[tail-1]+1]*num[q[tail-1]+1]; int yj=dp[q[tail]][j-1]+num[q[tail]+1]*num[q[tail]+1]; int yi=dp[i][j-1]+num[i+1]*num[i+1]; int xk=2*num[q[tail-1]+1]; int xj=2*num[q[tail]+1]; int xi=2*num[i+1]; if((yi-yk)*(xj-xk)<=(yj-yk)*(xi-xk))return 1; return 0; } bool get(int head,int j,int i) { int y1=dp[q[head]][j-1]+num[q[head]+1]*num[q[head]+1]; int y2=dp[q[head+1]][j-1]+num[q[head+1]+1]*num[q[head+1]+1]; int x1=num[q[head]+1]; int x2=num[q[head+1]+1]; if((y2-y1)<=2*num[i]*(x2-x1))return 1; return 0; } int main() { int n,m,t; int ca=1; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&num[i]); sort(num+1,num+n+1); int tail,head; for(int i=1;i<=n;i++) dp[i][1]=(num[i]-num[1])*(num[i]-num[1]); for(int j=2;j<=m;j++) { head=tail=0; q[++tail]=j-1; for(int i=j;i<=n;i++) { while(tail-head>1&&check(j,tail,i))tail--; q[++tail]=i; while(tail-head>1&&get(head+1,j,i))head++; int best=q[head+1]; dp[i][j]=dp[best][j-1]+(num[i]-num[best+1])*(num[i]-num[best+1]); } } printf("Case %d: %d ",ca++,dp[n][m]); } return 0; }
四边形不等式优化：
#include<cstdio> #include<cstring> #include<algorithm> #define maxn 10005 #define maxm 5005 #define inf 99999999 using namespace std; int dp[maxn][maxm]; int s[maxn][maxm]; int num[maxn]; int main() { int n,m; int t,ca=1; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i=1; i<=n; i++) scanf("%d",&num[i]); sort(num+1,num+1+n); dp[0][0]=1; for(int i=1; i<=n; i++) { dp[i][1]=(num[i]-num[1])*(num[i]-num[1]); } for(int j=2; j<=m; j++) { s[n+1][j]=n-1; for(int i=n; i>=j; i--) { dp[i][j]=inf; for(int k=s[i][j-1]; k<=s[i+1][j]; k++) { int tmp=dp[k][j-1]+(num[i]-num[k+1])*(num[i]-num[k+1]); if(dp[i][j]>tmp) { s[i][j]=k; dp[i][j]=tmp; } } } } printf("Case %d: %d ",ca++,dp[n][m]); } return 0; }