SRM 515 div1 med:NewItemShop

問題

TopCoder Statistics - Problem Statement

解法

基本的に状態として[持ってる刀の数][時間][どの客が来たかのフラグ]というのを持ってdpすれば大丈夫です。
ただ,客が最高で24人いるわけなので,どの客が来たかのフラグというのは2^24通りになってこれでは状態数が多すぎます。

しかし,客が来たかのフラグは「ある客が来たらもう別の客は来ない」という図式が成り立っている客のグループだけ管理されていれば良いので,フラグは客のグループの数分だけあれば良いとわかります。グループの数はたかだか24/2 = 12グループしかないのでこうすると状態数は24*25*2^12となり計算が間に合います。

以下のソースコードは計算量的にかなり雑に書いてますがtopcoderのサーバは速いので問題ありません。

struct cust {
    int t, cost, p;
    int g;
};
vector<cust> customer;

double dp[25][24][1<<13];

double dfs(int rest, int t, int state) {
    if (t >= 24) return 0;
    if (rest == 0) return 0;
    bool exist = false;
    double& ret = dp[rest][t][state];
    if (ret >= 0) return ret;
    ret = 0;
    for (cust C : customer) {
        if (C.t != t) continue;
        if (C.g != -1 && ((state>>C.g) & 1)) break;
        exist = true;
        // 来る
        double sum = 100;
        if (C.g != -1) {
            for (cust CC : customer) {
                if (CC.g == C.g && CC.t < C.t) sum -= CC.p;
            }
        }
        {
            int nstate = state;
            if (C.g != -1) nstate |= (1<<C.g);
            ret = max(C.cost+dfs(rest-1, t+1, nstate), dfs(rest, t+1, nstate));
            ret *= C.p/sum;
        }
        // 来ない
        {
            ret += (sum-C.p)/sum * dfs(rest, t+1, state);
        }
        break;
    }
    if (!exist) return ret = dfs(rest, t+1, state);
    return ret;
}

class NewItemShop {
public:
    double getMaximum(int swords, vector <string> customers) {
        for (int i = 0; i < 25; i++) for (int j = 0; j < 24; j++) {
            for (int k = 0; k < (1<<13); k++) dp[i][j][k] = -1;
        }
        int group = 0;
        customer.clear();
        for (string s : customers) {
            vector<cust> v;
            int cur = 0;
            while (cur < s.size()) {
                int now = 0;
                cust C;
                C.g = -1;
                while (s[cur] != ',' && cur < s.size()) {
                    now = now*10 + s[cur]-'0';
                    cur++;
                }
                C.t = now;
                cur++;
                now = 0;
                while (s[cur] != ',' && cur < s.size()) {
                    now = now*10 + s[cur]-'0';
                    cur++;
                }
                C.cost = now;
                cur++;
                now = 0;
                while (s[cur] != ' ' && cur < s.size()) {
                    now = now*10 + s[cur]-'0';
                    cur++;
                }
                C.p = now;
                v.push_back(C);
                cur++;
            }
            if (v.size() > 1) {
                for (cust &C : v) {
                    C.g = group;
                }
                group++;
            }
            for (cust C : v) customer.push_back(C);
        }
        //        for (cust C : customer) {
        //            cout << C.t << "  " << C.cost << "  " << C.p << "  " << C.g << endl;
        //        }
        return dfs(swords, 0, 0);
    }
};