SRM #528 Div.1 Medium - SPartition
出典
TopCoder Single Round Match 528 - Div. 1 Medium
概要
{x,o}^*を順序を変えずに抜き出して、残ったのと同じ文字列になる場合の数を求める
今何文字目かと、片方だけ取った文字列でメモ化再帰
二等分してそれぞれ全列挙してくっつけてもいいらしい
ソース
#include <string> #include <map> #include <iostream> using namespace std; class SPartition { private: string str; int n; map<pair<string, int>, long long> memo; public: long long getCount(string s) { str = s; n = s.length(); return solve(0, ""); } long long solve(int i, string x) { if (x.length() > n - i) { return 0; } if (i == n) { return 1; } pair<string,int> key = pair<string,int>(x, i); if (memo.count(key)) { return memo[key]; } long long ret = 0; if (x.length() == 0) { ret += solve(i+1, string(1, str[i])) * 2; } else { ret += solve(i+1, x + str[i]); if (str[i] == x[0]) { string nextX = x.substr(1); ret += solve(i+1, nextX); } } memo[key] = ret; // cout << i << "," << x << ":" << ret << endl; return ret; } };