SRM680 Div1 Easy "BearFair"

問題

TopCoder Statistics - Problem Statement

解法

こちらをチラ見しました（dpの作り方だけ。・・・・まあほとんど解答のようなものだけど・・・）
mayokoex.hatenablog.com

ありがとうございましたm(_ _)m

事後

チラ見してなお実装に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";
    }
};