HDOJ - 2375状态DP.. - c++编程基础

pizza总共只有15个..用二进制数表示当前选择了那些pizza..2^15-1=35535..dp[k]..k则是二进制状态的十进制值...dp[k]代表选择了这些pizza所需的最小费用..
用arc[y][x]记录拥有了y Pizza.. 则可以买x Pizza打arc[y][x]折...预处理中所有arc[y][x]=1..然后再更新arc...
更新..比如k=7, 二进制为111..由于是多了一个1...所以可能从h=110(6) or 101(5) o 011(3) 更新来的...本题说coupon可以合在一起用..那么将当前更新时h中所有对于当前选择添加x Pizza的discount相乘..再乘以x的原价...

Program:
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define oo 2000000000
#define pi acos(-1)
using namespace std;
struct node
{
int p,a;
}s[20];
double arc[20][20],dp[40000];
int n;
int main()
{
int i,j,m,h,k,x;
while (~scanf("%d",&n))
{
if (!n) break;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++) arc[i][j]=1;
for (i=0;i<=35000;i++) dp[i]=1e+30;
for (i=1;i<=n;i++)

{
scanf("%d%d",&s[i].p,&s[i].a);
dp[1<<(i-1)]=s[i].p;
scanf("%d",&m);
while (m--)
{
scanf("%d%d",&j,&x);
arc[i][j]=(100-x)/100.0;
}
}
double ans,area,data,M=(1< ans=1e+30;
for (h=1;h<=M;h++)
{
area=0;
for (x=1;x<=n;x++)
if (h & (1<<(x-1)))
{
area+=s[x].a;
k=h-(1<<(x-1));
data=1;
for (j=1;j<=n;j++)
if (k & (1<<(j-1))) data*=arc[j][x];
if (dp[h]>dp[k]+data*s[x].p)
dp[h]=dp[k]+data*s[x].p;
}
if (dp[h]/area }
printf("%.4lf\n",ans);
}
return 0;
}