まさにこれだったん。
CSA 069 DIV2 C Build Correct Brackets
()()))(())()
のようなカッコ列が与えられる。
最小回数flipして正しいカッコ列にせよ。
また最小回数flipで正しいカッコ列にする方法の数を数え上げよ。
・1 <= 文字列長 <= 2500
まさに最短路と一緒に最短路数も数え上げる問題。
正しい必要十分条件は、文字列を左から見ていって、
- ‘(‘ の数 - ‘)’ の数
が常に 0 以上であること。 なので
dp[ i+1 ][ j ] := i 文字目まで見て、’(‘ の数 - ‘)’ の数が j となるような最小の flip回数
num[ i+1 ][ j ] := またそのような場合の数
として DP を組む。
#include <iostream> using namespace std; string str; const long long MOD = 1000000007; const long long INF = 1LL<<59; long long dp[2600][2600]; long long num[2600][2600]; int main() { while (cin >> str) { for (int i = 0; i < 2600; ++i) { for (int j = 0; j < 2600; ++j) { dp[i][j] = INF; num[i][j] = 0; } } dp[0][0] = 0; num[0][0] = 1; for (int i = 0; i < str.size(); ++i) { for (int j = 0; j <= 2500; ++j) { if (str[i] == '(') { // same if (dp[i+1][j+1] > dp[i][j]) { dp[i+1][j+1] = dp[i][j]; num[i+1][j+1] = num[i][j]; } else if (dp[i+1][j+1] == dp[i][j]) { num[i+1][j+1] += num[i][j]; num[i+1][j+1] %= MOD; } // rev if (j > 0) { if (dp[i+1][j-1] > dp[i][j] + 1) { dp[i+1][j-1] = dp[i][j] + 1; num[i+1][j-1] = num[i][j]; } else if (dp[i+1][j-1] == dp[i][j] + 1) { num[i+1][j-1] += num[i][j]; num[i+1][j-1] %= MOD; } } } else { // same if (j > 0) { if (dp[i+1][j-1] > dp[i][j]) { dp[i+1][j-1] = dp[i][j]; num[i+1][j-1] = num[i][j]; } else if (dp[i+1][j-1] == dp[i][j]) { num[i+1][j-1] += num[i][j]; num[i+1][j-1] %= MOD; } } // rev { if (dp[i+1][j+1] > dp[i][j] + 1) { dp[i+1][j+1] = dp[i][j] + 1; num[i+1][j+1] = num[i][j]; } else if (dp[i+1][j+1] == dp[i][j] + 1) { num[i+1][j+1] += num[i][j]; num[i+1][j+1] %= MOD; } } } } } cout << dp[str.size()][0] << " " << num[str.size()][0] << endl; } }