SRM653 Div1 Easy "CountryGroupHard"
解法
dpる。
dp[i] := i-1番目の人までの、番号の振り方の場合の数
初期化
まだ誰にも番号を振っていないときは1パターンなので、
dp[0] = 1;
更新
i番目の人に1からi+1までの番号を振って、それぞれの場合の数を足しこんでいく
例えば、3番目(0-base)の人に2番を振れる場合、dp[2(3-2+1)]をdp[4(3+1)]に足すことになる。
結果
dp[n]が1なら"Sufficient"、それでなければ"Insufficient"
事後
うーん。。場合の数の数え上げの問題に変換できなかった。
Greedyから頭が離れず結局カンニング。
ソースコード
int dp[105]; class CountryGroupHard { public: string solve(vector<int> a) { int n = a.size(); int dp[n + 1]; // dp初期化 memset(dp, 0, sizeof(dp)); dp[0] = 1; // dp更新 for (int i = 0; i < n; i++) { for (int x = 1; x <= i + 1; x++) { bool ok = true; for (int c = i - x + 1; c <= i; c++) { if (a[c] != 0 && a[c] != x) ok = false; } if (ok) dp[i + 1] += dp[i - x + 1]; } } return (dp[n] == 1) ? "Sufficient" : "Insufficient"; } };