【bzoj 1190】梦幻岛宝珠（DP）

这题是在01背包问题的基础上，扩充了重量，需要用时间换空间。

思路：

1.仔细看题，注意到重量wi为a*2^b（a<=10，b<=30），很容易想到要按 b 分开做背包的DP。接下来的重点就是怎么使DP从b-1继承到b。

2.再仔细看题，发现只有一次询问，那么就可以在这个W上做文章——依W的大小进行所有的DP。由于是按b的大小进行DP，所以把数都看成二进制位来继承和转移，每对一组 b 相同的数做完后，就略去这一二进制位。

实现：

1.“去位”：若W的二进制数上第 i 位为1，那么这时背包里已经放的物品的重量的第 i 位为0或1都无所谓，装得了；若W的二进制数上第 i 位为0，那么背包已有的重量的第 i 位为1就要从二进制的前一位借一个“1”拿来用。

2.对每组 b 进行DP时，直接用最大的背包容量N*wi（mW），之后转移时再按W进行修改就行了。

其中，以上实现可行的原因是：

对于每个第 i 位，它处于一个很“尴尬”的境地，它的前一位一给就是给“1”，对于它就是“2”了，多了也无需退回去。因为对于每个第 j 位，它的下一位根本就帮不了它，贡献“1”对于它也只是“0.5”，是没有用的。因此要略去某一位时，只需干脆地按W是否能满足它这一位的需求来对自己的前一位进行调整。

 1 #include<cstdio>

 2 #include<cstdlib>

 3 #include<cstring>

 4 #include<iostream>

 5 #include<algorithm>

 6 using namespace std;

 7

 8 typedef long long LL;

 9 const int N=110,M=30,mW=1000;

10 int n,W;

11 struct node{int w,v,a,b;}s[N];

12 LL f[M+10][mW+10];

13

14 bool cmp(node x,node y)

15 {   return x.b<y.b;   }

16 LL mmax(LL x,LL y)

17 {   return x>y?x:y;   }

18

19 int main()

20 {

21     while (1)

22     {

23       scanf("%d%d",&n,&W);

24       if (n==-1&&W==-1) break;

25       for (int i=1;i<=n;i++)

26       {

27         scanf("%d%d",&s[i].w,&s[i].v);

28         s[i].a=s[i].w,s[i].b=0;

29         while (s[i].a%2==0) s[i].a/=2,s[i].b++;

30       }

31       sort(s+1,s+1+n,cmp);

32       int l,r;

33       l=1;

34       memset(f,0,sizeof(f));

35       for (int i=0;i<=M;i++)

36       {

37         r=l-1;//

38         while (r<n && s[r+1].b==i) r++;//<n

39         for (int j=l;j<=r;j++)

40          for (int k=mW;k>=s[j].a;k--)

41            f[i][k]=mmax(f[i][k],f[i][k-s[j].a]+s[j].v);

42         for (int j=0;j<=mW;j++)//or (int j=mW;j>=0;j--)

43           if (W&(1<<i)) f[i+1][j>>1]=mmax(f[i+1][j>>1],f[i][j]);

44           else f[i+1][(j+1)>>1]=mmax(f[i+1][(j+1)>>1],f[i][j]);

45         l=r+1;

46       }

47       printf("%lld\n",f[31][0]);

48     }

49     return 0;

50 }

巴特西

【bzoj 1190】梦幻岛宝珠（DP）

最新文章

热门文章