首页 > 代码库 > NOJ 1116 哈罗哈的大披萨 【淡蓝】 [状压dp+各种优化]

NOJ 1116 哈罗哈的大披萨 【淡蓝】 [状压dp+各种优化]

2024-08-04 21:40:18   222人阅读

我只能说，珍爱生命，远离卡常数的题。。。感谢陈老师和蔡神，没有他们，，，我调一个星期都弄不出来，，，，

 

哈罗哈的大披萨 【淡蓝】

时间限制(普通/Java) : 1000 MS/ 3000 MS          运行内存限制 : 65536 KByte
总提交 : 73            测试通过 : 9 

描述

热风哈罗哈（三牌楼）店正在搞活动：他们将提供一个大披萨给第一个告诉他们以下信息的人：一次购买任一种披萨，哪种单位面积的价格最低。问题初步想一想，好像是这么解决：“对于每个披萨计算平均价格，那么最小值就是答案了。”

但是，这个问题不是这么简单，因为在热风哈罗哈店里：对某些披萨，是送打折优惠券的，凭这些优惠券可以得到另一个便宜些甚至差点的披萨，这些优惠券可合并使用。披萨必须一个接一个的买，不可能使用优惠券对一个已买的披萨打折。你能第一个解决这个问题，得到大披萨吗？

输入

 

输入文件包含几个测试用例。每个测试用例包括：

l       1行：一个数m，为热风哈罗哈提供披萨数目。当m=0时输入终止。一般1 ≤ m ≤ 15。

l       随后的m 行描述每个披萨。每一行描述披萨i (1 ≤ i ≤ m) ，开始3个整数pi, ai 和 ni 表示披萨的价格、面积、和购买它时得到的打折优惠券数目，1 ≤ pi ≤ 10000, 1 ≤ ai ≤ 10000 , 0 ≤ ni < m。

l       随后是ni 对整数xi,j 和 yi,j 表示你得到打折的披萨序号xi,j (1 ≤ xi,j ≤ m, xi,j ≠ i) 以及买披萨xi,j得到的折扣yi,j，以百分比表示(1 ≤ yi,j≤ 50)。可以假设对于每个i ，xi,j 两两不同。

 

输出

 

对于每个测试用例:      

打印一行，为通过一次购买任何一种披萨所能得到的单位面积最低价钱. 四舍五入到小数点后4位。

注意到你能组合任意数目的打折优惠券：对于价格为10的披萨和两个折扣为50和20的优惠券，你将只需支付10 * 0.8 * 0.5 = 4单位的钱。

 

样例输入

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

题目来源

“IBM南邮杯”团队赛2009

 

题意不是很难，看到n=15我尝试了暴力、递归两种方法，T了之后乖乖地状压dp去了，用一个二进制数表示当前状态s，其中‘1’表示已经买过的pizza种类，然后依次去掉一个‘1’，得到s‘，由s‘可以转移得到s，dp[te]=mini(dp[te],dp[o]+p[k]*zhe[o][k] ); 其中p[k]代表第k种pizza的价格，zhe[o][k]代表的是第k种物品在状态s‘时所能获得的所有折扣，dp[te]表示状态s时最小的总价格。。。。然后，，，，就是一路优化常数的悲催经历了，，，感谢陈老师和蔡神，没有他们，，，我调一个星期都弄不出来，，，，

优化：

1.预处理了每个状态s时，第i种pizza所能得到的总折扣率。

2.去掉了位运算

3.预处理了每个状态中0的位置，0的总数

4.优化了dp顺序

5.还有各种稀奇古怪的，，，反正刚好不T了，我也就没管了，，，

附上题解：（来自陈老师）

Since each pizza can be bought at most once, we could solve the problem by enumerating all subsets of pizzas. However the order of buying the pizzas does matter, since coupons cannot be used retrospectively, and it is too slow to try all permutations of how to buy the pizzas.

The important observation is: given the subset of pizzas already bought, we do not care anymore about the order in which this subset of pizzas was bought. Therefore, we can use dynamic programming to solve this problem. We represent the subset of pizzas already bought by a bitmask with n bits, where bit i is set to 1 if and only if pizza i was already bought. The recurrence relation can be formulated as follows: minimum_price(mask) = minmask = submask + 2i minimum_price(submask) + price of pizza i where the price of pizza i is determined using discount coupons given for the pizzas bought before pizza i represented by the bitmask submask.

 

When calculating the minimum price for a subset of pizzas we only need to refer to bitmasks with a lower numeric value, therefore the recurrence relation can be calculated bottom up by enumerating all bitmasks with n bits from 0 to 2n-1. We need a table of size 2n, and each entry of the table can be calculated in O(n2) time, therefore the overall runtime is O(2n ⋅ n2).

 

Judges‘ test data consists of 37 test cases; most of them are random-generated.

 

ps:最后三个是我的代码，前面ac的都是蔡神的

 
5954njczy2010GAccepted12656 KB921 msGCC2612 B2014-11-27 22:08:52
5953njczy2010GAccepted12656 KB890 msG++2823 B2014-11-27 22:07:44
5951njczy2010GAccepted12656 KB921 msGCC2823 B2014-11-27 22:05:53
5949njczy2010GTime Limit Exceed at Test 1  GCC3044 B2014-11-27 21:55:45
5948njczy2010GTime Limit Exceed at Test 1  GCC3146 B2014-11-27 21:53:51
5947njczy2010GTime Limit Exceed at Test 1  GCC3150 B2014-11-27 21:47:58
5946njczy2010GTime Limit Exceed at Test 1  GCC2751 B2014-11-27 21:13:15
5924njczy2010GAccepted9312 KB750 msGCC2223 B2014-11-27 16:23:23
5918njczy2010GTime Limit Exceed at Test 1  GCC3162 B2014-11-27 16:14:19
5917njczy2010GTime Limit Exceed at Test 1  GCC2967 B2014-11-27 16:08:09
5916njczy2010GCompile Error  GCC2965 B2014-11-27 16:07:51
5915njczy2010GTime Limit Exceed at Test 1  GCC2851 B2014-11-27 16:05:25
5913njczy2010GTime Limit Exceed at Test 1  GCC2806 B2014-11-27 16:03:56
5911njczy2010GAccepted9312 KB859 msG++2215 B2014-11-27 15:53:04
5909njczy2010GTime Limit Exceed at Test 1  G++2996 B2014-11-27 15:52:13
5908njczy2010GTime Limit Exceed at Test 1  G++2692 B2014-11-27 15:26:46
5864njczy2010GTime Limit Exceed at Test 1  G++2482 B2014-11-27 11:57:07
5863njczy2010GTime Limit Exceed at Test 1  G++2428 B2014-11-27 11:55:09
5862njczy2010GTime Limit Exceed at Test 1  G++2416 B2014-11-27 11:50:31
5861njczy2010GTime Limit Exceed at Test 1  G++2406 B2014-11-27 11:44:55

 

这是水过去的代码：

 

  1 #include<stdio.h>  2   3 //#include<pair>  4   5 #define N 20  6 #define M 1005  7 #define mod 1000000007  8 //#define p 10000007  9 #define mod2 1000000000 10 #define ll long long 11 #define LL long long 12 #define eps 1e-9 13 #define maxi(a,b) (a)>(b)? (a) : (b) 14 #define mini(a,b) (a)<(b)? (a) : (b) 15  16 int m; 17 int x[N][N]; 18 double p[N],a[N],n[N],y[N][N]; 19 double zhe[ 32768 ][N]; 20 double ans; 21 double dp[ 32768 ]; 22 double tta[ 32768 ]; 23 int tot; 24 double zhezhe[N][N]; 25 int pos[ 32768 ]; 26 int son[ 32768 ]; 27 int pos2[ 32768 ][ 17 ]; 28 int cnt2[ 32768 ]; 29 int son2[ 32768 ][ 17 ]; 30 int h[16]; 31 char ss[17]; 32 int bit[32768][16]; 33  34 void ini1() 35 { 36     int i,o,j,k,ch; 37  38     h[0]=1; 39     for(i=1;i<16;i++) 40         h[i]=2*h[i-1]; 41     for(o=0;o<32768;o++){ 42         k=o; 43         j=0; 44         ch=1; 45         while(k > 0){ 46             bit[i][j] = k%2; 47             k = k/2; 48             j++; 49         } 50         for(j=0;j<15;j++) 51         { 52             if(bit[i][j]==0) 53             { 54                 pos2[o][ cnt2[o] ]=j; 55                 cnt2[o]++; 56             } 57             else 58             { 59                 if(ch==1) 60                 { 61                     ch=0; 62                     pos[o]=j; 63                     son[o]= o - h[j]; 64                 } 65             } 66         } 67     } 68 } 69  70 void ini() 71 { 72     ans=1000000000; 73     int i,j; 74     int o; 75     tot=h[m]; 76     for(i=1;i<=m;i++){ 77         for(j=1;j<=m;j++){ 78             zhezhe[i][j]=1.0; 79         } 80         scanf("%lf%lf%lf",&p[i],&a[i],&n[i]); 81         for(j=1;j<=n[i];j++){ 82             scanf("%d%lf",&x[i][j],&y[i][j]); 83             y[i][j]=(100.0-y[i][j])/100.0; 84             zhezhe[i][ x[i][j] ]=y[i][j]; 85         } 86     } 87  88     for(o=0;o<tot;o++){ 89         dp[o]=1000000000; 90  91     } 92     for(j=1;j<=m;j++){ 93         zhe[0][j]=1.0; 94     } 95     tta[0]=0.0; 96 } 97  98 void solve() 99 {100     int o,k,kk,j;101     int te;102     dp[0]=0;103     for(o=0;o<tot;o++){104         if(o>=1){105             j=pos[o]+1;106             te=son[o];107             tta[o]=tta[te]+a[j];108 109             for(kk=0;kk<cnt2[o];kk++){110                 k=pos2[o][kk]+1;111                 zhe[o][k]=zhe[te][k]*zhezhe[j][k];112             }113         }114 115         for(kk=0;kk<cnt2[o];kk++){116             k=pos2[o][kk]+1;117             te=o+h[k-1];118             dp[te]=mini(dp[te],dp[o]+p[k]*zhe[o][k] );119         }120     }121 }122 123 void out()124 {125     int o;126     for(o=1;o<tot;o++){127         //printf(" o=%d dp=%.4f\n",o,dp[o]);128         ans=mini(ans,dp[o]/tta[o]);129     }130     printf("%.4f\n",ans);131 }132 133 int main()134 {135     ini1();136    // freopen("data.in","r",stdin);137     //freopen("data.out","w",stdout);138     while(scanf("%d",&m)!=EOF)139     {140         if( m==0 ) break;141 142         ini();143         solve();144         out();145     }146 147     return 0;148 }

 

 

RunIDUserProblemResultMemoryTimeLanguageLengthSubmit Time
5860njczy2010GAccepted9312 KB734 msGCC2215 B2014-11-27 11:44:14
5859njczy2010GTime Limit Exceed at Test 1  GCC2215 B2014-11-27 11:43:42
5858njczy2010GTime Limit Exceed at Test 1  G++2404 B2014-11-27 11:36:29
5857njczy2010GTime Limit Exceed at Test 1  G++3036 B2014-11-27 11:24:57
5856njczy2010GTime Limit Exceed at Test 1  G++3466 B2014-11-27 11:13:39
5854njczy2010GTime Limit Exceed at Test 1  G++3413 B2014-11-27 11:07:27
5849njczy2010GTime Limit Exceed at Test 1  G++3722 B2014-11-27 10:23:56
5848njczy2010GCompile Error  G++3716 B2014-11-27 10:23:19
5847njczy2010GTime Limit Exceed at Test 1  G++3330 B2014-11-27 10:12:09
5846njczy2010GTime Limit Exceed at Test 1  G++3322 B2014-11-27 10:09:51
5845njczy2010GTime Limit Exceed at Test 1  G++3323 B2014-11-27 10:08:35
5844njczy2010GTime Limit Exceed at Test 1  G++3156 B2014-11-27 10:05:04
5842njczy2010GTime Limit Exceed at Test 1  GCC2916 B2014-11-26 23:30:18
5841njczy2010GTime Limit Exceed at Test 1  G++2986 B2014-11-26 23:23:18
5840njczy2010GWrong Answer at Test 1  G++2986 B2014-11-26 23:22:42
5839njczy2010GWrong Answer at Test 1  G++2984 B2014-11-26 23:19:33
5838njczy2010GWrong Answer at Test 1  G++2982 B2014-11-26 23:18:46
5837njczy2010GTime Limit Exceed at Test 1  G++2981 B2014-11-26 23:07:33
5836njczy2010GTime Limit Exceed at Test 1  G++2715 B2014-11-26 22:58:10
5830njczy2010GTime Limit Exceed at Test 1  G++2167 B2014-11-26 22:28:24

NOJ 1116 哈罗哈的大披萨 【淡蓝】 [状压dp+各种优化]


联系
我们