思路:
首先排序,然后也是划分题型,在i的子串中选取j段
状态转移方程dp[i][j]=min{dp[k][j-1]+(a[i]-a[k+1])^2}
AC代码:
#include<stdio.h> #include<stdlib.h> #define N 10005 #define M 5005 #define inf 0x3f3f3f3f int dp[N][M]; int s[N][M]; int a[N]; int n,m; int cmp(const void *a,const void *b) { return *(int *)a-*(int *)b; } int main() { int i,j,k; int T; int cas=1; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(i=1;i<=n;i++) scanf("%d",&a[i]); qsort(a+1,n,sizeof(a[1]),cmp); for(i=1;i<=n;i++) { dp[i][1]=(a[i]-a[1])*(a[i]-a[1]); s[i][1]=1; } for(j=2;j<=m;j++) { s[n+1][j]=n-1; for(i=n;i>=j;i--) { dp[i][j]=inf; for(k=s[i][j-1];k<=s[i+1][j];k++) if(dp[k][j-1]+(a[i]-a[k+1])*(a[i]-a[k+1])<dp[i][j]) { s[i][j]=k; dp[i][j]=dp[k][j-1]+(a[i]-a[k+1])*(a[i]-a[k+1]); } } } printf("Case %d: %d\n",cas++,dp[n][m]); } return 0; }