https://www.bnuoj.com/bnuoj/problem_show.php?pid=51640
dp[i][j]表示前j个数，分成了i组，最小需要多少精力。
那么，求解订票dp[i][j]的时候，要么，第i组不做题，要么，第i组做1题、2题、3题....j题
先把数组排好序。然后暴力
dp[i][j] = dp[i - 1][j] //第i组不做题。
然后枚举一个k，表示[K.....j]是第i组做的题。那么就是dp[i - 1][k - 1] + (a[j] - a[k])^2
复杂度是O（n^3）
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> #include <bitset> const int maxn = 500 + 20; int a[maxn]; LL dp[maxn][maxn]; void work() { int n, m; 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[0][i] = 1e18; dp[0][0] = 0; for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { dp[i][j] = dp[i - 1][j]; for (int k = 1; k <= j; ++k) { dp[i][j] = min(dp[i][j], dp[i - 1][k - 1] + 1LL * (a[j] - a[k]) * (a[j] - a[k])); } } } printf("%lld ", dp[m][n]); } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif int t; scanf("%d", &t); while (t--) work(); return 0; }