SRM 515 DIV1 550pt

题目大意：

n个人进入商店买东西，对于每个顾客都有T、C、P这3个数组，表示有Pj的概率第i个顾客在Tj的时间进入商店以Cj的价格买东西，每个顾客Pj的和小于等于1，保证每个时间只最多只有一个顾客可能会来，每个顾客只进入商店一次。一共有swords个物品，当一个顾客进来买东西的时候，售货员可以选择卖或不卖，她以之后的最大期望进行选择。问收银额的期望是多少。

解题思路：

当每个顾客可能来商店的时间只有一个的时候，题目比较简单，用dp[时间][剩下物品个数]的dp方程就可以解决。

当有顾客可能来商店的时间超过一个的时候，情况有点复杂，因为计算到下一个时间的时候，该顾客会不会出现的概率跟之前他有没有出现有关：如果之前他出现过了，那么这个时刻该顾客出现的概率为0；如果他之前没出现过，那个这个时间该顾客出现的概率是条件概率=原本的概率/(1-之前出现的概率和)。于是用一个位压缩状态来保存之前该顾客有没有出现。由于可能来商店的时间超过一个的顾客数量最多是24/2=12个，这样可以减少空间和时间。

之前没意识到这个是条件概率，一下子懵了，囧。。。。。

// BEGIN CUT HERE

#include <sstream>

/*

*/

#define debuging

#ifdef debuging

#define FIN  {freopen("new.in" , "r" , stdin) ;}

#define FOUT {freopen("new.out" , "w" , stdout) ;}

#define OUT(x)  {cout<< #x << "  : " << x <<endl ;}

#define ERR(x)  {cout<<"#error: "<< x ; while(1) ;}

#endif

// END CUT HERE

#ifndef debuging

#define FIN  ;

#define FOUT ;

#define OUT(x)  ;

#define ERR(x)  ;

#endif

#include <cstdio>

#include <iostream>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <vector>

#include <map>

using namespace std ;

#define For(i , n) for(int i = 0 ; i < (n) ; ++i)

#define SZ(x)  (int)((x).size())

#define clr(a,b) memset(a,b,sizeof(a))

#define mpr(a,b) make_pair(a,b)

typedef long long lint ;

const int maxint = -1u>> ;

const double eps = 1e- ;

double dp[<<][][];

class NewItemShop

{

public:

    int peo[],cost[];double p[];

    char str[];int sw;

    int sam[];

    double dfs(int mask,int swords,int tim){

        double &s=dp[mask][swords][tim];

        if(s>-0.5)return s;

        if(tim==||swords==)return s=;

        if(peo[tim]==-)return s=dfs(mask,swords,tim+);

        if(peo[tim]==-){

            s=p[tim]*max(dfs(mask,swords-,tim+)+cost[tim],dfs(mask,swords,tim+));

            s+=(-p[tim])*dfs(mask,swords,tim+);

            return s;

        }else{

            if(!(mask&(<<peo[tim])))return s=dfs(mask,swords,tim+);

            s=p[tim]*max(dfs(mask^(<<peo[tim]),swords-,tim+)+cost[tim],dfs(mask^(<<peo[tim]),swords,tim+));

            s+=(-p[tim])*dfs(mask,swords,tim+);

            return s;

        }

    }

    double getMaximum(int swords, vector <string> customers)

    {

        clr(peo,-);sw=swords;

        int n=customers.size();

        int cnt=;

        for(int i=;i<n;i++){

            string s=customers[i];

            int now=;double tmp=;sam[i]=;

            vector<int>vec;vec.clear();

            while(now<(int)s.size()){

                int a,b;double c;

                int k=;

                while(now<(int)s.size()&&s[now]!=' '){

                    str[k]=s[now];k++;now++;

                }

                now++;

                str[k]=;

                sscanf(str,"%d,%d,%lf",&a,&b,&c);

                peo[a]=i;cost[a]=b;p[a]=c//tmp;

                tmp-=c/;

                vec.push_back(a);

            }

            if(vec.size()==){

                peo[vec[]]=-;

            }else{

                for(int i=;i<(int)vec.size();i++)

                    peo[vec[i]]=cnt;

                cnt++;

            }

        }

        for(int i=;i<<<cnt;i++)

            for(int j=;j<=swords;j++)

                for(int k=;k<=;k++)

                    dp[i][j][k]=-;

        double ans=dfs((<<cnt)-,swords,);

        return double(ans) ;

    }

};