很坑爹的题目，3 A:100 A:200 A:400 这种算A的单项大于600，我最开始看题以为这种数据不需要丢弃，导致wrong了好几次
接下来就是简单的01背包了，做完这题之后在网上看别人的代码，发现看不懂。。 然后研究了很久，发现这堆看不懂的代码都是水过去的，他们都过不了下面这组数据
1000 32 A:200 A:4001 A:5001 C:400999 32 A:200 A:4001 A:5001 C:4003.00 141 A:0.011 A:0.021 A:0.041 A:0.081 A:0.161 A:0.321 A:0.641 A:1.281 A:2.561 A:5.121 A:10.241 A:20.481 A:40.961 A:81.92
我至今也没看懂他们代码想干啥，但是我能确定他们代码有问题。而且好多人的代码都错了。
我的代码如下
#include <stdio.h>#include <stdlib.h>#include <string.h>char dp[3000010];char dp2[3000010];int max ;int main(){ char buf[64]; int n; int flag = 1; int price; char *pbuf; float price_temp; int need_price; int total_price[30]; int i,j; int m; int a,b,c; while(scanf("%f%d", &price_temp, &n) != -1) { if(n == 0) break; memset(total_price, 0, sizeof(total_price)); memset(dp, 0, sizeof(char) * n * 100000 + 1); memset(dp2, 0, sizeof(char) * n * 100000 + 1); max = 0; need_price = (int)(price_temp*100); for(i = 0; i < n; i++) { scanf("%d", &m); flag = 1; a = 0; b = 0; c = 0; for(j = 0; j < m; j++) { scanf("%s", buf); if(buf[0] == 'A' || buf[0] == 'B' || buf[0] == 'C') { price = atoi(&buf[2]); if(price > 600) { flag = 0; } price*=100; if((pbuf = strstr(buf, ".")) != NULL) { price+= atoi(pbuf+1); } if(buf[0] == 'A') { a += price; } else if(buf[0] == 'B') { b += price; } else if(buf[0] == 'C') { c += price; } if(a > 60000 || b > 60000 || c > 60000) { flag = 0; } total_price[i] += price; if(total_price[i] > 100000) { flag = 0; } } else { flag = 0; } if(flag == 0) { total_price[i] = 0; } } } dp[0] = 1; dp2[0] = 1; for(i = 0; i < n; i++) { price = total_price[i]; if(price == 0) continue; for(j = 0; j <= max && j <= need_price; j++) { if(dp[j] == 1) { dp2[j + price] = 1; } } max += price; memcpy(dp, dp2, (max+1) * sizeof(char)); } if(need_price > 100000*30) i = 100000*30; else i = need_price; for(; i >=0; i--) { if(dp[i] == 1) { printf("%.2lf\n", (double)i/100); break; } } } return 0;}
