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:
[cpp] 
#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; 
}