Codeforces #204 Div1. C. Jeff and Brackets

本番時間切れだった問題。
http://codeforces.com/contest/351/problem/C

問題

regular bracket sequenceって一般用語なのかな？
要は開きかっこと閉じかっこだけで構成されており、開きかっこと閉じかっこの対応がとれた文字列らしい。

長さN×Mのregular bracket sequenceを構築したい。
ここで、i文字目を開きかっこにするコストをA[i%N]、閉じかっこにするコストをB[i%N]とする。
N,M,A,Bが与えられたとき、題意を満たすregular blacket sequenceの総コストを最小化せよ。

解法

N<=20と小さくM<=10^7とかなり大きい。
なので、中盤は開きかっこと閉じかっこの差分が増えないようにしていけばよい。
ただ、N文字たどる間に一時的に開きかっこが減る可能性があるので、最初に開きかっこを増やし、中盤は差分を保持し、最後に閉じかっこを置いて差分を０にすればよい。

中盤のコストを求めるため、今開きかっこがX個余分にあり、2N文字分括弧を配置して、また開きかっこがX個に戻るときの最少コストC[X]をDPで求める。

最初のN文字で開きかっこがX個余分になり、次の(M-2)個を上記手順でコストC[X]*(M-2)/2で配置し、最後のN文字で開きかっこを0個にしたのが総コストになる。
各Xについて総コストを求め、最小値をとったものが答え。

C[X]の算出にO(N^3)かかるが、N<=20なので余裕。Mの大きさは計算量に関係しない。

int N,M;
int A[100],B[100];
ll dpdp[41][41][41];
ll dpdp2[2][41];

void solve() {
	int f,r,i,j,k,l, x,y;
	
	cin>>N>>M;
	FOR(i,N) cin>>A[i];
	FOR(i,N) cin>>B[i];
	FOR(x,41) FOR(y,41) FOR(i,41) dpdp[x][y][i]=1LL<<40;
	
	FOR(y,2*N+1) {
		dpdp[y][0][y]=0;
		FOR(i,2*N) FOR(x,2*N+1) {
			if(x<2*N) dpdp[y][i+1][x+1]=min(dpdp[y][i+1][x+1],dpdp[y][i][x]+A[i%N]);
			if(x>0) dpdp[y][i+1][x-1]=min(dpdp[y][i+1][x-1],dpdp[y][i][x]+B[i%N]);
		}
	}
	
	ll re =1LL<<40;
	FOR(i,N+1) re = min(re,dpdp[0][N][i]+dpdp[i][N][0]+dpdp[i][2*N][i]*(M/2-1));
	cout << re << endl;
	
	return;
}

まとめ

N<=20って珍しい制限だな。
logMになるような処理を期待してたのかな？