HDOJ - 2375 状态DP.

HDOJ - 2375 状态DP..

     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:

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<map>
#include<queue>
#include<stack>
#include<set>
#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<<n)-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<ans) ans=dp[h]/area;
           }
           printf("%.4lf\n",ans);
    }
    return 0;
}