TopCoder SRM 653 Div2 Hard SingingEasy

題名通りDiv1 Mediumよりすんなり。
http://community.topcoder.com/stat?c=problem_statement&pm=13685

問題

N個の音符からなり、それぞれ音の高さがP[i]である歌がある。
この歌の各音符を2人で分担して歌う。

各人の歌う歌の難しさは、隣接する歌う音符の高さの差の絶対値の総和である。
2人で最適に音符を分担したとき、2人の歌の難しさの総和を最小化せよ。

解法

2人が最後に歌った音符の番号をx,yとし、DP[x][y]=(難しさの総和の最小値)、としてDPしていく。

こう書くと、z番目の音符をどちらが歌うか考える際、0≦x,y＜zの範囲を考えないといけないので全体でO(N^3)かかりそうに見える。
ただし、実際はz番目の音符をどちらが歌うか考える際、z-1番目の音符は2人のどちらかが必ず歌っているので、0≦x,y＜zの範囲のうちx=z-1またはy=z-1であるものだけ考えればよく、結局O(N^2)で解ける。

ll dp[2020][2020];

class SingingEasy {
	public:
	int solve(vector <int> pitch) {
		int N=pitch.size(),x,y;
		FOR(x,N+3) FOR(y,N+3) dp[x][y]=1LL<<60;
		
		dp[1][0]=0;
		for(x=2;x<=N;x++) {
			for(y=0;y<=x-2;y++) {
				dp[y][x]=min(dp[y][x],dp[y][x-1]+((x-2>=0)?abs(pitch[x-1]-pitch[x-2]):0));
				dp[x][y]=min(dp[x][y],dp[x-1][y]+((x-2>=0)?abs(pitch[x-1]-pitch[x-2]):0));
				dp[x][x-1]=min(dp[x][x-1],dp[y][x-1]+((y>0)?abs(pitch[x-1]-pitch[y-1]):0));
				dp[x-1][x]=min(dp[x-1][x],dp[x-1][y]+((y>0)?abs(pitch[x-1]-pitch[y-1]):0));
			}
		}
		
		ll mi=1LL<<60;
		for(y=0;y<=N-1;y++) mi=min(mi,dp[y][N]);
		for(y=0;y<=N-1;y++) mi=min(mi,dp[N][y]);
		return mi;
	}
}

まとめ

DPの状態遷移をちょっと工夫すると、あっさり解ける問題。