#DP #Expectation #MaxMinExpectation #TopCoder #Solved

NewItemShop.cpp

//https://arena.topcoder.com/#/u/practiceCode/14606/17786/11508/1/309624
#include <bits/stdc++.h>

#define ll long long
#define sz(v) ((int) ((v).size()))
#define clr(v, d) memset(v, d, sizeof(v))
#define lp(i, n) for(int i = 0; i < (int)(n); ++i)
#define rep(i, v) for(int i = 0; i < sz(v); ++i)

using namespace std;

const int MAX = 15;
const int OO = 1e4;
int n = 24, swords;

double cache[25][25][4500];
int customers[25];
double prob[25];
int cost[25];

int getBit(int mask, int indx) {
    return (mask>>indx)&1;
}

int setBit1(int mask, int indx) {
    return mask | (1<<indx);
}

double calcMaxExpect(int i, int s, int mask) {
    while(customers[i] == -1 && i != 24) i++;
    if(i == n || s == 0)
        return 0;
    double &ret = cache[i][s][mask];
    if(ret + 1.0 > 1e-9)
        return ret;
    ret = 0.0;

    double ch1 = calcMaxExpect(i+1, s, mask);

    if(getBit(mask, customers[i]))
        return ret = ch1;
    int tmpmask = customers[i] < 12 ? setBit1(mask, customers[i]) : mask;
    double ch2 = calcMaxExpect(i+1, s, tmpmask);

    double ch3 = cost[i] + calcMaxExpect(i+1, s-1, tmpmask);

    return ret = (1-prob[i])*ch1 + prob[i] * max(ch2, ch3);

}

bool cmp(string a, string b) {
    return count(a.begin(), a.end(), ' ') > count(b.begin(), b.end(), ' ');
}
/*
int main() {
    int m;
    cin>>swords;
    cin>>m;
    string cust[25];string foos;
    getline(cin, foos);
    lp(i, m) {
        getline(cin, cust[i]);
    }
    clr(cache, -1);
    clr(customers, -1);
    sort(cust, cust+m, cmp);

    lp(i, m) {
        istringstream iss(cust[i]);
        int t, c;
        double p, pp = 1.0;
        char foo;

        while(iss>>t>>foo>>c>>foo>>p) {
            customers[t] = i;
            p /= 100.0;
            prob[t] = p/pp;
            pp -= p;
            cost[t] = c;
        }

    }
    cout << calcMaxExpect(0, swords, 0) << endl;
    return 0;
}
*/
class NewItemShop {
public:
    double getMaximum(int swords, vector<string> cust) {
        clr(cache, -1);
        clr(customers, -1);
        sort(cust.begin(), cust.end(), cmp);

        rep(i, cust) {
            istringstream iss(cust[i]);
            int t, c;
            double p, pp = 1.0;
            char foo;

            while(iss>>t>>foo>>c>>foo>>p) {
                customers[t] = i;
                p /= 100.0;
                prob[t] = p/pp;
                pp -= p;
                cost[t] = c;
            }

        }
        return calcMaxExpect(0, swords, 0);
    }
};