当前位置:编程学习 > C/C++ >>

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; 

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,