首页 > ACM题库 > HDU-杭电 > hdu 2375 Help Bob-状态DP[解题报告]C++
2014
01-05

hdu 2375 Help Bob-状态DP[解题报告]C++

Help Bob

问题描述 :

Bob loves Pizza but is always out of money. One day he reads in the newspapers that his favorite pizza restaurant, Alfredo’s Pizza Restaurant, is running a competition: they will donate a big pizza to the first person who will tell them the lowest price per area that can be achieved by buying any of the pizzas at most once. "That task is easy!", thinks Bob, "For each pizza I just calculate the average price and the lowest quotient will be the answer.".

Unfortunately the problem is a bit more complicated: with some pizzas Alberto gives out discount coupons for getting another pizza cheaper and even worse, those coupons can be combined. The pizzas have to be bought one after the other, and it is not possible to use a coupon to get a discount retrospectively for a pizza which has already been bought. Can you help Bob to become the first to solve this task and to get a pizza for free?

输入:

The input file contains several test cases. Each test case starts with a number m, the number of pizzas Alfredo offers. Input is terminated by m=0. Otherwise, 1 ≤ m ≤ 15. Then follow m lines describing the pizzas. Each of those following lines describes pizza i (1 ≤ i ≤ m) and starts with 3 integer numbers pi, ai and ni specifying the price of the pizza, its area and the number of discount coupons you get when buying it, 1 ≤ pi ≤ 10000, 1 ≤ ai ≤ 10000 and 0 ≤ ni < m. Then follow ni pairs of integer numbers xi,j and yi,j specifying the index xi,j (1 ≤ xi,j ≤ m, xi,j ≠ i) of the pizza you get a discount coupon for and the discount in percentage terms yi,j (1 ≤ yi,j ≤ 50) you get when buying pizza xi,j. You may assume that for each i the values xi,j are pairwise distinct.

输出:

The input file contains several test cases. Each test case starts with a number m, the number of pizzas Alfredo offers. Input is terminated by m=0. Otherwise, 1 ≤ m ≤ 15. Then follow m lines describing the pizzas. Each of those following lines describes pizza i (1 ≤ i ≤ m) and starts with 3 integer numbers pi, ai and ni specifying the price of the pizza, its area and the number of discount coupons you get when buying it, 1 ≤ pi ≤ 10000, 1 ≤ ai ≤ 10000 and 0 ≤ ni < m. Then follow ni pairs of integer numbers xi,j and yi,j specifying the index xi,j (1 ≤ xi,j ≤ m, xi,j ≠ i) of the pizza you get a discount coupon for and the discount in percentage terms yi,j (1 ≤ yi,j ≤ 50) you get when buying pizza xi,j. You may assume that for each i the values xi,j are pairwise distinct.

样例输入:

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


状态压缩DP:
纪念一下.
代码:

#include <iostream>
using namespace std;

template <class T> void out(T x, int n){ for (int i = 0; i < n; ++i) cout << x[i] << ' '; cout << endl; }
template <class T> void out(T x, int n, int m){ for (int i = 0; i < n; ++i) out(x[i], m); cout << endl; }

#define OUT(x) (cout << #x << " = " << x << endl)
#define FOR(i, a, b) for(int i = (int)a; i < (int)b; ++i)
#define REP(i, b) FOR(i, 0, b)
#define FORD(i, a, b) for(int i = (int)a; i >= (int)b; --i)
#define MAXN 20
#define MAXX (1<<16)
#define Inf 1e20

#define IN(x, tmp) ((tmp>>x)&1)

double disCount[MAXN][MAXN];
double price[MAXN], area[MAXN];
double f[MAXX];
double ans;
int n, m;

void input(){
int t, xi;
double yi;
REP (i, n)
REP (j, n)
disCount[i][j] = 1.0;

REP (i, n)
{
scanf("%lf %lf %d", &price[i], &area[i], &t);
while (t--)
{
scanf("%d %lf", &xi, &yi);
disCount[i][xi-1] *= (100.0-yi)*0.01;
}
}
}

void solve(){
double area0;
m = 1<<n;
REP (i, m) f[i] = Inf;

ans = Inf;
f[0] = 0;

REP (tmp, m)
{
if (Inf == f[tmp]) continue;
area0 = 0;

REP (j, n)
{
if (IN(j, tmp))
{
area0 += area[j];
}
else
{
double cost = price[j];
REP (i, n)
{
if (IN(i, tmp)) cost *= disCount[i][j];
}

int temp = tmp | (1<<j);
cost += f[tmp];

if (f[temp] > cost)
{
f[temp] = cost;
}
}
}
if (tmp) ans = min(ans, f[tmp]/area0); 
}

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

}

int main(){
while (EOF != scanf("%d", &n))
{ 
if (0 == n) break;
input();
solve();
}
return 0;
}

 


  1. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.

  2. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3

  3. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥