TopCoder SRM 787 : Div2 Hard AqaAsadiGroups

今回レート反映遅いんだけど何なんだろうね。
https://community.topcoder.com/stat?c=problem_statement&pm=16214&rd=17994

問題

N要素の整数列Aが与えられる。
AをK個の部分列に分割したとする。(長さ0の要素があってもよい)

Aの総和をSとすると、各部分列の平均値はS/kになることが期待できる。
i番目の部分列の総和をG[i]としたとき、sum*1^2)なので、三重ループで解ける。

int S[505];
ll dp[501][501];
class AqaAsadiGroups {
	public:
	long long minimumDifference(vector <int> Skills, int k) {
		int N=Skills.size();
		int x,y,z,i;
		FOR(i,N) S[i+1]=S[i]+Skills[i];
		int sum=S[N];
		FOR(x,501) FOR(y,501) dp[x][y]=1LL<<60;
		dp[0][0]=0;
		FOR(x,k) {
			FOR(y,N+1) {
				for(z=y;z<=N;z++) dp[x+1][z]=min(dp[x+1][z],dp[x][y]+1LL*(sum-(S[z]-S[y])*k)*(sum-(S[z]-S[y])*k));
			}
		}
		
		return dp[k][N];
	}
}

まとめ

900～950ptでもいい気がする。

*1:S/k-G[i])^2)の最小値を求めよ。 (S-k*G[i])^2の最小値を求めることを考えよう。 dp(a,n) := Aのうちprefix n要素から部分列a個を作ったときのそこまでのsum((S-k*G[i])^2)の最小値 a+1番目の部分列を[n,m)とするとdp(a+1,m) = min(dp(a,n) + (S-k*sum(A[n...m]