TopCoder SRM 787 : Div1 Medium AqaAsadiTrains

本番全然わからなかった。
https://community.topcoder.com/stat?c=problem_statement&pm=16214&rd=17994

問題

整数列Aが与えられる。
各要素はk未満の非負整数とする。

この数列に対し、以下の処理を行うことができる。

• 1要素を指定し取り除く。取り除く値がvの時、スコアC[v]を得る(負の場合もある)
• 隣接する2要素を指定し、1つの別の値に入れ替える。2要素の値a,bにより、入れ替え先の値T(a,b)は決められており、対応表は入力で与えられる。

数列の全要素を取り除くまで処理を繰り返してもよいし、途中で終えてもよい。
得るスコアの総和の最大値を求めよう。

dp(L,R,v) := 元の数列の区間[L,R)の範囲で処理を繰り返し、最後に1つvが要素として残る場合の総スコア
とする。すると2つの隣接区間に対応するdp(L,M,a)とdp(M,R,b)から、以下の遷移が可能である。

• 前者のaを取り除き、dp(L,R,b) = dp(L,M,a)+dp(M,R,b)+C[a]
• 後者のbを取り除き、dp(L,R,a) = dp(L,M,a)+dp(M,R,b)+C[b]
• 2つを入れ替え
  • dp(L,R,T(a,b)) = dp(L,M,a)+dp(M,R,b)
  • dp(L,R,T(b,a)) = dp(L,M,a)+dp(M,R,b)

あとはAを分割したとき、その位置をX1,X2,X3....とすると
max(dp(0,X1,a1) + max(0,C[a1]) + dp(X1,X2,a2) + max(0,C2) + ....)
を取る。maxの部分は、区間を代表して最後に残った値を取り除くか取り除かないかのそれぞれを考えた場合である。

int tab[100][100];
ll dp[51][51][51];
ll ret[51];

class AqaAsadiTrains {
	public:
	int getMax(vector <int> C, vector <int> A, vector <int> T) {
		int K=C.size();
		int N=A.size();
		
		int x,y,z,i,a,b;
		FOR(x,51) FOR(y,51) FOR(z,51) dp[x][y][z]=-1LL<<60;
		FOR(x,N) dp[x][x+1][A[x]]=0;
		
		FOR(y,K) FOR(x,K) tab[y][x]=T[y*K+x];
		
		for(int len=2;len<=N;len++) {
			for(x=0;x+len<=N;x++) {
				for(y=x+1;y<x+len;y++) {
					FOR(a,K) FOR(b,K) {
						dp[x][x+len][a]=max(dp[x][x+len][a],dp[x][y][a]+dp[y][x+len][b]+C[b]);
						dp[x][x+len][b]=max(dp[x][x+len][b],dp[x][y][a]+dp[y][x+len][b]+C[a]);
						dp[x][x+len][tab[a][b]]=max(dp[x][x+len][tab[a][b]],dp[x][y][a]+dp[y][x+len][b]);
						dp[x][x+len][tab[b][a]]=max(dp[x][x+len][tab[b][a]],dp[x][y][a]+dp[y][x+len][b]);
					}
				}
			}
		}
		
		for(i=1;i<=N;i++) {
			ret[i]=ret[i-1];
			FOR(x,i) FOR(y,K) ret[i]=max(ret[i],ret[x]+dp[x][i][y]+max(0,C[y]));
		}
		return ret[N];
		
	}
}

まとめ

これ解法に至らなかったの残念。