天上掉Pizza

题目描述
明明喜欢Pizza，但总是缺钱。有一天，他在报纸上阅读，他最喜爱的比萨饼店��必胜客，正在对大批新Pizza运行的促销。促销的办法是：在购买一些Pizza后，可能得到一些优惠券，可以对另一些Pizza进行打折，更令人惊喜的是这些优惠券可以结合起来。但是，有一个限制，Pizza必须一个接一个买，而后得到的优惠券也不可能追溯前面已经买过的Pizza。明明想尝试若干新品Pizza，可又没有充足的钱，为了能省一些，明明费劲脑力，就请你帮他计算一下如何购买Pizza，使得其平均价格最低！平均价格是指买到Pizza的总价格/总面积，即单位面积的Pizza的价格。还要注意，“安排顺序”只要求按照给定的顺序安排每个操作。不一定是各机器上的实际操作顺序。在具体实施时，有可能排在后面的某个操作比前面的某个操作先完成。
输入
有多组输入数据。
每组输入数据第一行为m(1<=m<=15).
接下来m行，每行前3个数pi,ai,ni(1<=pi<=10000,1<=ai<=10000,0<=nipi为编号为i的Pizza的价格，ai为编号为i的Pizza的面积，ni为购买i号Pizza能得到ni张优惠券
接下来ni*2个数，分别表示该张优惠券对xi号Pizza打折(1<=xj<=m,i<>xj)，折扣为yj(1<=yj<=50)
输入以m=0结束。

输出
输出购买m个Pizza中某一些的最低单位面积价格。保留4位小数。
(如果一个Pizza原价10，得到了一张50和一张20的优惠券，那么购买它实际所需的价值就是10*0.5*0.8=4)

样例输入
1
80 30 0
2
200 100 1 2 50
200 100 0
5
100 100 2 3 50 2 50
100 100 1 4 50
100 100 1 2 40
600 600 1 5 10
1000 10 1 1 50
0
样例输出
2.6667
1.5000
0.5333
提示
Pizza可以不全部购买

可以看出此题我们可以用状压DP，令f[i]为以i为状态时用的最少的钱（以i为状态意味将i写作二进制每位上0或1代表这块pizza是否买了）。答案求的是单位面积的最小价格，但来记录单位面积的价格对于我们处理起来是非常麻烦的，我们可以想到对于一种状态时pizza的面积是确定的，我们只需要记录最小价格就好了。最终求答案只需将整个DP数组扫一遍，找出价格除以面积最小的就好了。在转移时我们可以枚举现在要买哪个pizza（记为x，当然这个pizza是还没有买过的），然后枚举当前状态已买的pizza中优惠x的优惠券，计算出这个pizza在用了优惠券后的价格即可。
（DP转移方程见代码）

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,p[20],a[20],num[20],x[20][20],y[20][20],s[20][40000];
double f[20][40000];
bool flag[20][40000];
int main()
{
    while (true)
    {
        scanf("%d",&n);
        if (n==0) break;
        for (int i=1;i<=n;i++)
        {
            scanf("%d%d%d",&p[i],&a[i],&num[i]);
            for (int j=1;j<=num[i];j++) scanf("%d%d",&x[i][j],&y[i][j]);
        }   
        memset(f,127,sizeof(f));
        memset(flag,1,sizeof(flag));
        f[0][0]=0;s[0][0]=0;flag[0][0]=0;
        for (int i=1;i<=n;i++)
            for (int j=0;j<=(1<<n)-1;j++)
            if (flag[i-1][j]!=1)
            {
                for (int k=1;k<=n;k++)
                if ((j&(1<<(k-1)))==0)
                {
                    int t=j,x1=0;
                    double w=p[k];
                    while (t!=0)
                    {
                        x1++;
                        if (t%2==1)
                        {
                            for (int l=1;l<=num[x1];l++) 
                            if (x[x1][l]==k) w=w*(double)(100-y[x1][l])/100;
                        }
                        t/=2;
                    }
                    f[i][j|(1<<(k-1))]=min(f[i][j|(1<<(k-1))],f[i-1][j]+w);
                    s[i][j|(1<<(k-1))]=s[i-1][j]+a[k];
                    flag[i][j|(1<<(k-1))]=0;
                }
            }
        double ans=1<<29;
        for (int i=1;i<=n;i++)
            for (int j=1;j<=(1<<n)-1;j++) 
            if (flag[i][j]==0) ans=min(ans,f[i][j]/s[i][j]);
        printf("%.4f\n",ans);
    }
    return 0;
}