天上掉Pizza

时间限制: 3 Sec 内存限制: 128 MB
提交: 73 解决:
48
[提交][状态][讨论版]

题目描述

明明喜欢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

样例输出

提示

Pizza可以不全部购买

一眼看下去也许没什么思路，阅读量有些大，还好输出那里有些提示，看m的范围，也就是披萨总数可以发现，可以将披萨压缩，

表示为已经买了哪几个披萨，因此dp[x]表示买了x状态的披萨的最小那个什么。。

和导游2还是有些类似的，但这里需要预处理出买了第几个披萨对其他披萨的优惠，这样一个数组，然后和导游2的转移差不多类似。

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<iostream>

#include<cstring>

#include<string>

using namespace std;

const int MAXN=;

struct fzy

{

    double s,fee,ave;

    void init()

    {

        s=fee=ave=-;

    }

}dp[(<<)+];

double g[MAXN][MAXN];

int a[MAXN],p[MAXN];

int n,num;

void init()

{

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

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

            g[i][j]=;

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

        dp[i].init();

}

void dfs(int sta,int num)

{

    if (num==)

    {

        dp[sta].s=;

        dp[sta].fee=;

        dp[sta].ave=;

        return;

    }

    if (dp[sta].fee>) return;

    double rs,rf,ra=<<MAXN;

    int xx;

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

    {

        if ((<<i)&sta)

        {

            xx=sta^(<<i);

            dfs(xx,num-);

            double x=p[i+]*1.0;

            for (int ii=;ii<n;ii++)

                if ((<<ii)&xx)

                {

                    x*=g[ii+][i+];

                }

            x+=dp[xx].fee;

            if (x<ra) ra=x;

        }

    }

    dp[sta].fee=ra;

}

double min(double a,double b)

{

    return a>b?b:a;

}

int main()

{

    while (scanf("%d",&n)&&n)

    {

        init();

        int num,x,y;

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

        {

            scanf("%d%d%d",&p[i],&a[i],&num);

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

            {

                scanf("%d%d",&x,&y);

                g[i][x]=(-y*1.0/);

            }

        }

        dfs((<<n)-,n);

        double ans=<<MAXN;

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

        {

            dp[i].s=;

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

                if (i&(<<j)) dp[i].s+=a[j+];

            dp[i].ave=dp[i].fee/dp[i].s;

        }

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

            ans=min(ans,dp[i].ave);

        printf("%.4f\n",ans);

    }

}