Codeforces 351(#204 Div1) C. Jeff and Brackets

問題

長さnの数列a[i], b[i]が与えられる。
長さnmの対応の取れた括弧の列を書く。i番目に開き括弧を書くときコストa[i % n]が、
i番目に閉じ括弧を書くときコストb[i % n]がかかる。

長さnmの括弧の列を書く最小のコストを求めよ。

制約条件

n≦20
m≦10^7

方針

長さnの括弧の列をブロックと呼ぶ。

全体で、括弧の深さは2n以下であるとしてよい。
（深さがnを超えた時点で、その先で使う予定であった括弧が浅くなるブロックを持ってきてもコストが同じだから）

なので、一つのブロックで深さがsからtへ変化するときのコストの最小値をDPで求めておけば、
行列A[s][t]をm乗することで長さnmのときのコストの最小値がわかる。
ただし、ここでの掛け算C = A * Bは、C[i][j] = min{A[i][k] + B[k][j]}である。

editorial曰く、実際にはもっと強く括弧の深さはn以下としてよいらしい。
（証明は宿題、らしい。+6 +6 +6 +6 -8 -8 -8が最適のときとかどうするんだろ）

ソースコード

typedef vector<vi> M;
inline M operator*(const M & a, const M &b){
	M c(a.size(), vi(b[0].size(), inf));
	rep(i, c.size()) rep(j, c[0].size()) rep(k, a[0].size())
		c[i][j] = min(c[i][j], a[i][k] + b[k][j]);
	return c;
}
inline M pow(M a, ll m){
	M res = a; m--;
	for(; m; m /= 2){
		if(m & 1) res = res * a;
		a = a * a;
	}
	return res;
}
int n, m, a[20], b[20];
int main(){
	cin >> n >> m;
	rep(i, n) cin >> a[i];
	rep(i, n) cin >> b[i];
	
	M A(n + 1, vi(n + 1));
	
	rep(s, n + 1){
		static int dp[21][21];
		rep(i, n + 1) rep(j, n + 1) dp[i][j] = 1e9;
		dp[0][s] = 0;
		rep(i, n) rep(j, n + 1) if(dp[i][j] < 1e9){
			if(j + 1 <= n) dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + a[i]);
			if(j - 1 >= 0) dp[i + 1][j - 1] = min(dp[i + 1][j - 1], dp[i][j] + b[i]);
		}
		rep(t, n + 1) A[s][t] = dp[n][t];
	}
	A = pow(A, m);
	cout << A[0][0] << endl;
	
	return 0;
}