POJ 1742 Coins ( 单调队列解法 )
发布日期:2021-08-21 02:35:27 浏览次数:8 分类:技术文章

本文共 1656 字,大约阅读时间需要 5 分钟。

做题感悟:第一次做的时候用的二进制优化。可是没注意到是险过。so也没去看单调队列的解法。

解题思路:

                 假设你做过单调队列的题,或者看过相关的博客就好理解这题了。。

再加上这题体积与价值相等那么就更好做了。仅仅有 j %v[ i ] 余数同样的才干够同一时候处理(j 指的是某个体积的值),在计算某个数的时候,仅仅要计算前面的同样的余数中(在个数限制内)是否有 true(有放满的) 就能够了。

代码:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std ;#define INT long long int#define L(x) (x * 2)#define R(x) (x * 2 + 1)const int INF = 0x3f3f3f3f ;const double esp = 0.0000000001 ;const double PI = acos(-1.0) ;const int mod = 1000000007 ;const int MY = (1<<5) + 5 ;const int MX = 100010 + 5 ;int n ,W ,ans ;int v[MX] ,num[MX] ;bool deq[MX] ,dp[MX] ;void input(){ memset(dp ,false ,sizeof(dp)) ; for(int i = 1 ;i <= n ; ++i) scanf("%d" ,&v[i]) ; for(int i = 1 ;i <= n ; ++i) scanf("%d" ,&num[i]) ;}void DP(int v ,int num){ if(!num || !v) return ; if(num == 1) // 01 背包 { for(int i = W ;i >= v ; --i) if(!dp[i] && dp[i-v]) dp[i] = true ,ans++ ; } else if(num * v >= W) // 全然背包 { for(int i = v ;i <= W ; ++i) if(!dp[i] && dp[i-v]) dp[i] = true ,ans++ ; } else { num = min(num ,W/v) ; for(int a = 0 ;a < v ; ++a) // 同样余数一块处理 { int front =0 ,end = 0 ,sum = 0 ; for(int j = a ;j <= W ; j += v) { if(end - front-1 == num) // 去除过时元素 ,由于最多选择num[i] 个 sum -= deq[front++] ; deq[end++] = dp[j] ; // 存入 sum += dp[j] ; if(!dp[j] && sum) dp[j] = true ,ans++ ; } } }}int main(){ //freopen("input.txt" ,"r" ,stdin) ; while(scanf("%d%d" ,&n ,&W) ,n+W) { input() ; dp[0] = true ; ans = 0 ; for(int i = 1 ;i <= n ; ++i) DP(v[i] ,num[i]) ; printf("%d\n" ,ans) ; } return 0 ;}

转载地址:https://blog.csdn.net/weixin_33708432/article/details/86321243 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:Android获取 应用程序大小,数据大小,缓存大小
下一篇:Ruby测试小代码[计算50以内的素数]

发表评论

最新留言

第一次来,支持一个
[***.219.124.196]2024年03月20日 13时43分28秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

php编码函数 base58,1. Base58可逆加密 2019-04-21
oracle 在需要下列之一,Oracle存储过程中PLS-00103:出现符号“/”在需要下列之一时:(... 2019-04-21
oracle10g dblink优化,Oracle10g通过dblink访问数据异常 2019-04-21
linux安装时的iso文件,直接用ISO文件在linux上安装新系统 2019-04-21
linux修改文件权限为所有人都可以访问,Linux 笔记分享八:文件权限的设定 2019-04-21
linux中卸载ambri-servle,Kerberos 命令使用 2019-04-21
linux二进制反编译,Xori:一款来自BlackHat 2018的二进制反汇编和静态分析工具 2019-04-21
linux两台主机添加信任,Linux两台机器间添加信任,实现不用密码问,互传文件... 2019-04-21
linux 自动获取ssl证书,linux生成自验证ssl证书的具体命令和步骤 2019-04-21
linux基础命令20个,20-linux中基础命令 2019-04-21
重置网络配置 android,重置Android移动网络信号? 2019-04-21
java约瑟夫环pta上_cdoj525-猴子选大王 (约瑟夫环) 2019-04-21
java++记录+运行_记录java+testng运行selenium(三)---xml、ini、excel、日志等配置 2019-04-21
mysql居左查询abcd_MySql速查手册 2019-04-21
loadrunner 错误: 无法找到 java.exe_LoadRunner错误及解决方法总结 2019-04-21
Java小魔女芭芭拉_沉迷蘑菇不可自拔,黏土人《小魔女学园》苏西·曼芭芭拉 图赏... 2019-04-21
php+mysql记事本_一个简单记事本php操作mysql辅助类创建 2019-04-21
300小时成为java程序员_直击面试现场: Java程序员3轮6小时面试, 成功拿到阿里offer!... 2019-04-21
中国网建java发送短信_短信验证登陆-中国网建提供的SMS短信平台 2019-04-21
隔行变色java代码_jquery入门—选择器实现隔行变色实例代码 2019-04-21