こちらは焦って手抜き回答でMLEしてしまった。
http://codeforces.com/contest/571/problem/B
問題
n要素の数列Aが与えられる。
Aの要素を任意に並べ替えられるとき、整数kに対してを最小化せよ。
解法
Aを昇順ソートした数列をBとする。
(Aを0-originで考えると)、数式の値は|A[0]-A[k]| + |A[k]-A[2*k]| + .... + |A[1]-A[1+k]| + |A[1+k]-A[1+2*k]| ...
となるので、A[0],A[k],A[2k]...を順にB[0],B[1],B[2]...と代入していけば良い。
このように、Bの連続した要素をA[i*k+j]=B[j*(n/k)+i]のように代入していくと良い。
ただ、n%kが0以外の時注意が必要である。
A[j],A[k+j],A[2k+j]...A[(n/k)*k+j]の数列は、要素数が(n/k)個ものが(k-(n%k))個、(n/k+1)個のものが(n%k)個ある。
つまりこの問題は以下のように言い換えられる。
Bを昇順ソートし、それらを要素数が(n/k)個ものが(k-(n%k))個、(n/k+1)個のものが(n%k)個の連続した要素群に分類する。
各要素群における最大値と最小値の差の総和を最小化せよ。
この問題ではkが5000以下のため、Bの先頭i要素をどう分類するかに対し、
dp[要素数(n/k)個の要素群の数][要素数(n/k+1)個の要素群の数] := i個目までの要素を(n/k)個または(n/k+1)個単位で分類したときの、各要素群における最大値と最小値の差の総和の最小化
としてDPしていけば良い。
最初のソートと合わせて、O(N*logN+K^2)で終わる。
int N,K; ll A[303030]; ll dp[5050][5050]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>K; FOR(i,N) cin>>A[i]; sort(A,A+N); int step=N/K; int large=N%K,small=K-large; memset(dp,0x7f,sizeof(dp)); dp[0][0]=0; FOR(x,large+1) FOR(y,small+1) { int pos=x*(step+1)+y*step; if(x<large) dp[x+1][y]=min(dp[x+1][y],dp[x][y]+A[pos+step]-A[pos]); if(y<small) dp[x][y+1]=min(dp[x][y+1],dp[x][y]+A[pos+step-1]-A[pos]); } cout<<dp[large][small]<<endl; }
まとめ
この回はホント雑すぎた。