SRM 653 div1 easy:CountryGroupHard
TopCoderのDP難しい。
問題:http://community.topcoder.com/stat?c=problem_statement&pm=13688
解法:メモ化再帰を使う。メモしておく量は、dp[start][end] = (区間[start,end)だけで座ってる人の国の並び方を考えた時、並び方は何通りあるか)とする。
まず、end == start の時は区間がないので1通り。end < startとなることは関数の仕様上ない気がするが一応0を返すようにした。
次に、それ以外の場合を考える。基本的には、この区間の中に0以外の数字が入っていないと複数通り解釈ができることになる。ただ区間の長さが1で0があるときはこの区間内に1人の国があると解釈できるのでその場合は1通り。
区間内に0でない数があった時、その人数をp人とすると、その区間内にp人の並びがあるはずである。それを全探索して、何通りがあり得るかを調べる。
以下ソースコード
typedef long long ll; const int MAXN = 128; int dp[MAXN][MAXN]; vector<int> aa; // [start,end)の範囲では何通りの可能性があるかを調べる int dfs(int start, int end) { if (end == start) return 1; if (end < start) return 0; int& ret = dp[start][end]; if (ret >= 0) return ret; ret = 0; int i; for (i = start; i < end; i++) { if (aa[i] > 0) break; } if (i == end) return ret = end-start; // 最初の位置はi-aa[i]+1からiのどれか for (int j = i-aa[i]+1; j <= i; j++) { int ng = 0; for (int x = 0; x < aa[i]; x++) { if (j+x < start || j+x >= end) { ng++; break; } if (aa[j+x] != 0 && aa[j+x] != aa[i]) { ng++; break; } } if (ng) continue; ret += dfs(start, j) * dfs(j+aa[i], end); } return ret = min(ret, 2); } class CountryGroupHard { public: string solve(vector <int> a) { aa = a; int n = a.size(); memset(dp, -1, sizeof(dp)); int ans = dfs(0, n); cout << ans << endl; if (ans == 1) return "Sufficient"; else return "Insufficient"; } };