TopCoder SRM 556 Div1 Medium LeftRightDigitsGame2

問題

それぞれに1つの数字が書かれたn枚のカードがあり、i番目のカードの数字はdigits[i]で表される。
1枚目のカードをまずテーブルに置き、2枚目以降のカードを次のようにおく。

  • 今までに置いたカード全部よりも右側に置く。
  • 今までに置いたカード全部よりも左側に置く。

こうして作れるすべてのカードを並べてできる数字のうち、
lowerBound以上の数字で最小のものを求めよ。
数字が作れないとき、空文字列を返せ。

制約条件

digitsとlowerBoundの長さは同じで、50以下

方針

DP.
dp[l][r][k]を、完成後の数字のl文字目からr文字目までを作っていて、
k = 0のとき[l, r)がlowerBoundに一致、
k = 1のとき[l, r)がlowerBoundより小
k = 2のとき[l, r)がlowerBoundより大
であるようなときの、最小値とする。


これに対してカードを一枚ずつ左か右に置くことで更新していくDPをすればいい。
時間計算量O(n^2).

ソースコード

const string BIG =":";
string dp[51][51][3]; //eq, sml, big

class LeftRightDigitsGame2 {
	public:
	string minNumber(string digits, string lowerBound) {
		int n = digits.size();
		rep(i, n + 1) rep(j, n + 1) rep(k, 3) dp[i][j][k] = BIG;
		
		rep(i, n + 1) dp[i][i][0] = "";
		rep(s, n) rep(l, n - s + 1) rep(k, 3){
			int r = l + s;
			int nk;
			if(dp[l][r][k] == BIG) continue;
			if(l > 0){
				if(digits[s] != lowerBound[l - 1]) nk = digits[s] < lowerBound[l - 1] ? 1 : 2;
				else nk = k;
				dp[l - 1][r][nk] = min(dp[l - 1][r][nk], digits[s] + dp[l][r][k]);
			}
			if(r < n){
				if(k != 0) nk = k;
				else if(digits[s] != lowerBound[r]) nk = digits[s] < lowerBound[r] ? 1 : 2;
				else nk = 0;
				dp[l][r + 1][nk] = min(dp[l][r + 1][nk], dp[l][r][k] + digits[s]);
			}
		}
		string ans = min(dp[0][n][0], dp[0][n][2]);
		return ans == BIG ? "" : ans;
	}
};