TopCoder SRM 667 Div2 Hard ShopPositions

これは典型かな…。
http://community.topcoder.com/stat?c=problem_statement&pm=13884

問題

N個のビルが１列に並んでおり、各ビルにはMフロアがある。
これらのビル群にタコスを売る店を作りたい。
各ビルには１フロアにつき１つまで店を作れる。

ただし店を作りすぎると、個々の店の売り上げは減少する。
各店の売り上げは、x番目のビルに店を作ったとき、そのビルと両隣のビル中における店の数をyとするとP[x][y]となる。
P[x][y]はyに関して降順である。

N,M,Pが与えられるとき、売り上げの総和を最大化せよ。
(PはP[x][y]=C[x*3+M+y-1]で換算できる１次元配列Cで与えられる。)

解法

左端のビルから順にDPしていくだけ。
左隣のビルの店舗数を覚えてDPしていくのは当然として、右隣のビルの店舗数が0～Mの場合を先読みかつ総当たりしながらDPしていけば良い。
O(N*M^3)で処理できる。

class ShopPositions {
	int P[32][1000];
	ll dp[33][33][33];
	
	public:
	int maxProfit(int n, int m, vector <int> c) {
		int b,i,x;
		int pre,cur,ne;
		
		ZERO(P);
		FOR(i,n) for(x=1;x<=3*m;x++) P[i][x] = c[i*3*m+x-1];
		
		memset(dp,0xff,sizeof(dp));
		for(i=0;i<=m;i++) dp[0][0][i]=0;
		
		FOR(b,n) {
			FOR(pre,m+1) FOR(cur,m+1) FOR(ne,m+1) dp[b+1][cur][ne] = max(dp[b+1][cur][ne], dp[b][pre][cur]+cur*P[b][pre+cur+ne]);
		}
		ll ma=0;
		FOR(cur,m+1) FOR(ne,m+1) ma=max(ma,dp[n][cur][ne]);
		return ma;
	}
}

まとめ

両隣状態に依存して値が決まる場合、直前の状態に加え1手先まで先読みするのは定番テクだね。