AUPC 2018 day3: G Palindromic Subsequences
問題
英小文字からなる文字列が与えられる。
文字列の必ずしも連続しない部分文字列のうち、回文であるものは何種類あるか。
同じ回文は一つと数える。
制約
文字列の長さ2000以下。
方針
回文を外側から作っていくDPを考える。
dp[i][j] := i文字目以前まで使いi文字目は必ず使い、j文字目以降とj文字目は必ず使い回文になっている文字列の個数。
遷移するときに、同じ回文は一つと数えるためには、使える文字のうち最も外側にあるものだけを使うようにすればいい。
よくあるユニークな必ずしも連続しない部分文字列を数えるDPほぼそのまま。
ソースコード
string s; int n, r[2001][26], l[2001][26]; const int mod = 1e9 + 7; int dp[2001][2001]; int main() { cin.tie(0); cin.sync_with_stdio(0); cin >> s; n = s.size(); rep(i, n + 1) rep(j, 26) r[i][j] = l[i][j] = -1; rep(i, n) rep(j, 26) l[i][j] = s[i] - 'a' == j ? i : i ? l[i - 1][j] : -1; for(int i = n - 1; i >= 0; i--) rep(j, 26) r[i][j] = s[i] - 'a' == j ? i : r[i + 1][j]; dp[0][n] = 1; using ll = long long; ll ans = 0; for(int w = n; w >= 1; w--) rep(i, n - w + 1){ int j = i + w; if(!dp[i][j]) continue; rep(c, 26){ int p = r[i][c]; int q = l[j - 1][c]; if(p < 0 || q < 0 || p >= j || q < i) continue; ans += (p != q ? 2ll : 1ll) * dp[i][j]; (dp[p + 1][q] += dp[i][j]) %= mod; } } cout << ans % mod << endl; return 0; }