【bzoj 1190】梦幻岛宝珠(DP)
2018-06-17 23:47:55来源:未知 阅读 ()
这题是在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 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:spfa
- bzoj3569 DZY Loves Chinese II 2020-05-25
- bzoj4036 [HAOI2015]按位或 2020-04-26
- 「BZOJ4173」数学 2020-01-15
- bzoj3944 Sum 2019-12-25
- BZOJ1008: [HNOI2008]越狱(快速幂) 2019-08-26
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash