题意：一个n个元素的集合S要求分成m个子集且子集并为S，要求$\sum_{S_i} (MAX-MIN)^2$最小。（n<=10000, m<=5000）
#include#include #include #include #include using namespace std;const int N=10005;typedef long long ll;ll d[2][N];int n, p, x[N], s[2][N];inline ll sqr(ll a) { return a*a; }inline ll w(int i, int j) { return sqr(x[j]-x[i]); }int main() { int T; scanf("%d", &T); for(int __=1; __<=T; ++__) { scanf("%d%d", &n, &p); for(int i=1; i<=n; ++i) scanf("%d", &x[i]); sort(x+1, x+1+n); int h=0, t=1; for(int i=2; i<=n; ++i) d[h][i]=w(1, i), s[h][i]=1; for(int i=2; i<=p; ++i) { s[t][n+1]=n; for(int j=n; j>=1; --j) { int l=s[h][j], r=s[t][j+1], &pos=s[t][j]; ll &now=d[t][j]; now=~0ull>>1; for(int k=l; k<=r; ++k) { ll t=d[h][k-1]+w(k, j); if(now>=t) now=t, pos=k; } } swap(t, h); } printf("Case %d: %lld\n", __, d[h][n]); } return 0;}
看完题目就知道很简单= =可是看到数据范围的时候傻了= =就算$O(n^2)$也不能这样卡是不是！！
可是发现时限5s！！！
于是同上一题一样，详细看上一题题解= =