题目
定义状态dp[i][j]表示排序后前i个数分成j组的最小花费。
dp[i][j] = min(dp[k][j-1] + (a[i]-a[k+1])^2)
dp[i][j] = min(dp[k][j-1] + a[i]^2 + a[k+1]^2 - 2*a[i]*a[k+1])
dp[i][j] = min(dp[k][j-1] + a[k+1]^2 - 2*a[i]*a[k+1]) + a[i]^2
斜率优化。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 10010int dp[N][N], q[N], a[N];
int l, r, n, m;
int main(){int T, ad;ad = 0;scanf( "%d", &T);while ( T-- ){scanf( "%d%d", &n, &m);for ( int i = 1; i <= n; i++) scanf( "%d", &a[i]);sort(a+1, a+1+n);for ( int i = 1; i <= n; i++) dp[1][i] = (a[i]-a[1])*(a[i]-a[1]);for ( int i = 2; i <= m; i++){l = 0, r = 0;q[r++] = i-1;for ( int j = i; j <= n; j++){while ( l+1 < r ){int y1 = dp[i-1][q[l]] + a[q[l]+1]*a[q[l]+1];int y2 = dp[i-1][q[l]+1] + a[q[l+1]+1]*a[q[l+1]+1];int x1 = a[q[l]+1];int x2 = a[q[l+1]+1];if ( y1- 2*a[j]*x1 >= y2 - 2*a[j]*x2 ) l++;else break;}int k = q[l];dp[i][j] = dp[i-1][k] + (a[j]-a[k+1])*(a[j]-a[k+1]);while( l+1 < r ){int x1 = a[j+1] - a[q[r-1]+1];int y1 = dp[i-1][j] + a[j+1]*a[j+1] - ( dp[i-1][q[r-1]]+a[q[r-1]+1]*a[q[r-1]+1]);int x2 = a[q[r-1]+1] - a[q[r-2]+1];int y2 = dp[i-1][q[r-1]] + a[q[r-1]+1]*a[q[r-1]+1] -( dp[i-1][q[r-2]]+a[q[r-2]+1]*a[q[r-2]+1]);if (x1*y2-x2*y1 >= 0) r--;else break;} q[r++] = j;}}printf("Case %d: %d\n",++ad,dp[m][n]);}return 0;
}