哈罗哈的大披萨 【淡蓝】
时间限制(普通/Java) : 1000 MS/ 3000 MS 运行内存限制 : 65536 KByte
总提交 : 99 测试通过 : 14
比赛描述
热风哈罗哈（三牌楼）店正在搞活动：他们将提供一个大披萨给第一个告诉他们以下信息的人：一次购买任一种披萨，哪种单位面积的价格最低。问题初步想一想，好像是这么解决：“对于每个披萨计算平均价格，那么最小值就是答案了。”
但是，这个问题不是这么简单，因为在热风哈罗哈店里：对某些披萨，是送打折优惠券的，凭这些优惠券可以得到另一个便宜些甚至差点的披萨，这些优惠券可合并使用。披萨必须一个接一个的买，不可能使用优惠券对一个已买的披萨打折。你能第一个解决这个问题，得到大披萨吗？
输入
输入文件包含几个测试用例。每个测试用例包括：
l 1行：一个数m，为热风哈罗哈提供披萨数目。当m=0时输入终止。一般1 ≤ m ≤ 15。
l 随后的m 行描述每个披萨。每一行描述披萨i (1 ≤ i ≤ m) ，开始3个整数pi, ai 和 ni 表示披萨的价格、面积、和购买它时得到的打折优惠券数目，1 ≤ pi ≤ 10000, 1 ≤ ai ≤ 10000 , 0 ≤ ni < m。
l 随后是ni 对整数xi,j 和 yi,j 表示你得到打折的披萨序号xi,j (1 ≤ xi,j ≤ m, xi,j ≠ i) 以及买披萨xi,j得到的折扣yi,j，以百分比表示(1 ≤ yi,j ≤ 50)。可以假设对于每个i ，xi,j 两两不同。
输出
对于每个测试用例:
打印一行，为通过一次购买任何一种披萨所能得到的单位面积最低价钱. 四舍五入到小数点后4位。
注意到你能组合任意数目的打折优惠券：对于价格为10的披萨和两个折扣为50和20的优惠券，你将只需支付10 * 0.8 * 0.5 = 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
题目来源
“IBM南邮杯”团队赛2009
题目意思说的不是很清楚。可以买好多个披萨，但是必须一个一个买，买了一个披萨之后会得到相应的优惠券，然后可以用优惠卷买剩下的披萨。要求计算总的单位面积的披萨的最小值。
至于可以可以买重复的披萨，其实是无所谓的，因为优惠券不能对已经买的披萨打折。如果要第二次购买的披萨的单位面积价格比当前的平均价格高，买了之后会让平均价格变高，得不偿失，如果要购买的披萨比当前的平均价格低，那么一开始的时候只要购买这个不打折的披萨就好了。综上，不需要重复购买披萨。
下面就当做每个披萨只能购买一次来考虑。
使用状态压缩的办法，描述每种购买状态下将要购买某个披萨的折扣，以及初始化每个状态的总的披萨的面积，dp维护每种状态下，购买这些披萨的最小价钱。
算法时间复杂度：O（n22n）
修改优化的地方：
- 使用bit[N]数组来标记二进制标记位对应的披萨编号。
- 使用数组下标来标记折扣代表的披萨号。
- 使用dp的方法计算折扣。
最终AC代码
#include <iostream> #include <stdio.h> #include <vector> #include <cstring> using namespace std; int m, n, x; double p, a, y; double dp[1<<16 | 1]; double zhekou[1<<16 | 1][16]; double toarea[1<<16 | 1]; int bit[1 << 16 | 1]; struct Pizza { double p; double a; double Coupon[16]; }; Pizza pizza[16]; inline int lowbit(int i) { return i&(-i); } void read() { for(int i = 0; i < m; i++) { scanf("%lf%lf%d", &p, &a, &n); pizza[i].p = p; pizza[i].a = a; for(int j = 0; j < n; j++) { scanf("%d%lf", &x, &y); pizza[i].Coupon[x-1] = y; } } } void solve() { int maxs = 1 << m; for(int i = 0; i < m; i++) bit[1 << i] = i; toarea[0] = 0; for(int i = 1; i < maxs; i++) { int id = bit[lowbit(i)]; toarea[i] = toarea[i - lowbit(i)] + pizza[id].a; } dp[0] = 0; for(int s = 1; s < maxs; s++) dp[s] = 1e9; for(int s = 0; s < maxs; s++) { for(int i = 0; i < m; i++) { if((1 << i) & s) continue; zhekou[s][i] = 1.0; if(s) { int lowb = lowbit(s); int id = bit[lowb]; zhekou[s][i] = zhekou[s ^ lowb][i] * (100 - pizza[id].Coupon[i]) / 100.0; } dp[s ^ (1<<i)] = min(dp[s ^ (1<<i)], dp[s] + zhekou[s][i]*pizza[i].p); } } double ans = 1e10; for(int s = 0; s < maxs; s++) { ans=min(ans, dp[s] * 1.0 / toarea[s]); } printf("%.4f ", ans); } int main() { while(scanf("%d", &m) == 1, m) { read(); solve(); } return 0; }