SRM680 Div1 Easy "BearFair"
事後
チラ見してなお実装に75分かかるとはいったい・・・ウゴゴゴ・・・
貰うdpひさびさに実装したぞ~
ソースコード
bool dp[1010][55][55]; class BearFair { public: string isFair(int n, int b, vector<int> upTo, vector<int> quantity) { // dp初期化 for (int i = 0; i <= b; i++) { for (int o = 0; o <= n; o++) { for (int d = 0; d <= n; d++) { dp[i][o][d] = false; } } } dp[0][0][0] = true; // dp更新 for (int i = 1; i <= b; i++) { for (int o = 0; o <= n; o++) { for (int e = 0; o + e <= n; e++) { bool ok = true; // check!!! for (int j = 0; j < upTo.size(); j++) { if (i < upTo[j]) { // quantity兄貴より上回ることは許さん if (o + e > quantity[j]) ok = false; } else if (i == upTo[j]) { // quantity兄貴と同じでないと許さん if (o + e != quantity[j]) ok = false; } else { // quantity兄貴より下回ることは許さん if (o + e < quantity[j]) ok = false; } } if (!ok) continue; // printf("2 %d %d %d\r\n", i, o, e); if (i % 2 != 0) { // iが奇数だ! dp[i][o][e] = dp[i - 1][o - 1][e] | dp[i - 1][o][e]; } else { // iが偶数だ! dp[i][o][e] = dp[i - 1][o][e - 1] | dp[i - 1][o][e]; } } } } // 答え算出 bool ans = false; for (int i = 0; i <= b; i++) { ans |= dp[i][n / 2][n / 2]; } return ans ? "fair" : "unfair"; } };