采药

题目大意：

给出n个物品，每一个物品有一个体积和价值

给出背包的总体积T，求出最大价值

M,T<=100000

t,v<=10

这道题可能刚开始认为是一道01背包的问题，但是看到了数据范围发现01背包达到了10^10，所以01背包是行不通的

由于我们看到tv都很小，所以我们知道只有100种物品类型，而其余的都是重复的，那么我们就可以利用二进制拆分的原理，将相同的物品累加一下总数，将他们拆成大小不同的物品，那么这样就可以表示出所有的物品数，正确性？

任何数都可以用二进制进行表示，所以一定不会漏掉。

那么怎么拆呢？我们设一个base，模拟拆的过程，如果能拆出来就拆，到不能拆了为止就把剩余的数加入一个新的物品中。

关于时间复杂度，其实并不正确，考虑最坏的情况：均摊，那么每一个是1000个物品，拆完大约10个，那么总复杂度10^3*10^5就是10^8，这个可能需要一些优化才能卡过去吧。。。

最后，附上本题代码：

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 using namespace std;
 5 //Debug Yufenglin
 6 #define debugj printf("Running
");
 7 #define debugp1(x) printf("%d
",x);
 8 #define debugp2(x,y) printf("%d %d
",x,y);
 9 #define debugp3(x,y,z) printf("%d %d %d
",x,y,z);
10 
11 //Standfor Yufenglin
12 #define LL long long
13 #define LB long double
14 #define reg register
15 #define il inline
16 #define inf 1e8
17 #define maxn 100000
18 
19 int T,M;
20 struct medicine
21 {
22     int t,v,sum;
23 };
24 medicine med[maxn+5],c[maxn+5],ans[maxn+5];
25 int f[maxn+5],cnt,temp[50],num;
26 
27 int qpow(int x,int y)
28 {
29     int ans=1;
30     while(y!=0)
31     {
32         if(y&1)
33         {
34             ans*=x;
35         }
36         x*=x;
37         y>>=1;
38     }
39     return ans;
40 }
41 bool cmp(medicine x,medicine y)
42 {
43     if(x.t==y.t) return x.v>y.v;
44     return x.t>y.t;
45 }
46 int main()
47 {
48     scanf("%d%d",&M,&T);
49     for(int i=1; i<=M; i++)
50     {
51         scanf("%d%d",&med[i].t,&med[i].v);
52     }
53     sort(med+1,med+M+1,cmp);
54     for(int i=1; i<=M; i++)
55     {
56         if(med[i].t!=med[i-1].t||med[i].v!=med[i-1].v)
57         {
58             c[++cnt].t=med[i].t;
59             c[cnt].v=med[i].v;
60             c[cnt].sum++;
61         }
62         else
63         {
64             c[cnt].sum++;
65         }
66     }
67     for(int i=1; i<=cnt; i++)
68     {
69         int base=1;
70         while(c[i].sum>base)
71         {
72             c[i].sum-=base;
73             ans[++num].v=base*c[i].v;
74             ans[num].t=base*c[i].t;
75             base*=2;
76         }
77         ans[++num].v=c[i].sum*c[i].v;
78         ans[num].t=c[i].sum*c[i].t;
79     }
80     /*for(int i=1; i<=num; i++)
81     {
82         debugp2(ans[i].t,ans[i].v);
83     }*/
84     for(int i=1; i<=num; i++)
85     {
86         for(int j=T; j>=ans[i].t; j--)
87         {
88             f[j]=max(f[j],f[j-ans[i].t]+ans[i].v);
89         }
90     }
91     printf("%d
",f[T]);
92     return 0;
93 }