Time Limit: 3000MS | Memory Limit: 30000K | |
Total Submissions: 32955 | Accepted: 11199 |
Description
You are to write a program which reads n,m,A1,A2,A3...An and
C1,C2,C3...Cn corresponding to the number of Tony's coins of value
A1,A2,A3...An then calculate how many prices(form 1 to m) Tony can pay
use these coins.
Input
input contains several test cases. The first line of each test case
contains two integers n(1<=n<=100),m(m<=100000).The second line
contains 2n integers, denoting A1,A2,A3...An,C1,C2,C3...Cn
(1<=Ai<=100000,1<=Ci<=1000). The last test case is followed
by two zeros.
Output
Sample Input
3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0
Sample Output
8
4
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
int num[],v[];
int dp[][];
int main()
{
int n,m,now,pre;
while(~scanf("%d%d",&n,&m)&&n&&m)
{
for(int i=;i<=n;i++)scanf("%d",&v[i]);
for(int i=;i<=n;i++)scanf("%d",&num[i]);
memset(dp,,sizeof(dp));
for(int i=;i<=n;i++){
now=i%;pre=(i-)%;
dp[now][]=;
for(int j=;j<=m;j++){
if(dp[pre][j]<=num[i-])dp[now][j]=;
if(j>=v[i]&&dp[now][j-v[i]]+<=num[i])
dp[now][j]=min(dp[now][j],dp[now][j-v[i]]+);
}
} int ans=;
for(int i=;i<=m;i++)
if(dp[now][i]<=num[n])
ans++; printf("%d\n",ans);
}
return ;
}
动态规划(背包问题):POJ 1742 Coins的更多相关文章
-
hdu 2844 poj 1742 Coins
hdu 2844 poj 1742 Coins 题目相同,但是时限不同,原本上面的多重背包我初始化为0,f[0] = 1;用位或进行优化,f[i]=1表示可以兑成i,0表示不能. 在poj上运行时间正 ...
-
题解报告:hdu 2844 &; poj 1742 Coins(多重部分和问题)
Problem Description Whuacmers use coins.They have coins of value A1,A2,A3...An Silverland dollar. On ...
-
[POJ 1742] Coins 【DP】
题目链接:POJ - 1742 题目大意 现有 n 种不同的硬币,每种的面值为 Vi ,数量为 Ni ,问使用这些硬币共能凑出 [1,m] 范围内的多少种面值. 题目分析 使用一种 O(nm) 的 D ...
-
poj 1742 Coins (动态规划,背包问题)
Coins Time Limit: 3000MS Memory Limit: 30000K Total Submissions: 32977 Accepted: 11208 Descripti ...
-
poj 1742 Coins(dp之多重背包+多次优化)
Description People in Silverland use coins.They have coins of value A1,A2,A3...An Silverland dollar. ...
-
POJ 1742 Coins(多重背包, 单调队列)
Description People in Silverland use coins.They have coins of value A1,A2,A3...An Silverland dollar. ...
-
Poj 1742 Coins(多重背包)
一.Description People in Silverland use coins.They have coins of value A1,A2,A3...An Silverland dolla ...
-
poj 1742 Coins (多重背包)
http://poj.org/problem?id=1742 n个硬币,面值分别是A1...An,对应的数量分别是C1....Cn.用这些硬币组合起来能得到多少种面值不超过m的方案. 多重背包,不过这 ...
-
POJ 1742 Coins (多重背包)
Coins Time Limit: 3000MS Memory Limit: 30000K Total Submissions: 28448 Accepted: 9645 Descriptio ...
随机推荐
-
-[NSNull countByEnumeratingWithState:objects:count:]:
当数组为空时遍历数组容易出这样的问题, -[NSNull countByEnumeratingWithState:objects:count:]: unrecognized selector sent ...
-
NetworkComms框架介绍 完美支持TCP/UDP协议
NetworkComms网络通信框架序言 英文文章地址 :http://www.networkcomms.net/tcp-udp-connections/ NetworkComs.Net无缝的支持TC ...
-
easy ui 表单提交添加遮罩,避免数据重复提交
如下图: //点击提交按钮保存数据 $('#btn_submit').click(function () { //增加遮罩层 $.messager.progress({ title: '温馨提示', ...
-
Webapp meta标签解决移动缩放的问题
webapp开发初期,会碰到在pc端开发好的页面在移动端显示过大的问题,这里需要在html head中加入meta标签来控制缩放 <meta name=" viewport" ...
-
PHP Database ODBC 之 ODBC
ODBC 是一种应用程序编程接口(Application Programming Interface,API),使我们有能力连接到某个数据源(比如一个 MS Access 数据库). 创建 ODBC ...
-
【QT相关】QT+opencv环境配置
在qt msvc2010版软件中使用opencv2.4.9进行库函数配置.仅适用于windows下. INCLUDEPATH += $$PWD/../../../opencv/build/includ ...
-
Delphi判断一个字符是否为汉字的最佳方法
//判断字符是否是汉字 function IsHZ(ch: WideChar): boolean; var i:integer; begin i:=ord(ch); if( i<19968) o ...
-
python实战第一天-paramiko模块并练习
操作系统 Ubuntu 15.10 IDE & editor JetBrains PyCharm 5.0.2 ipython3 Python版本 python-3.4.3 安装paramiko ...
-
Vue.js02:数据绑定v-model用法
<!-- v-model 实现数据的双向绑定 --> <!-- v-model 只能用在表单元素中 --> 示例: <!DOCTYPE html> <!-- ...
-
js如何复制一个对象?
方法一: 把原来对象的属性遍历一遍,赋给一个新的对象. //深复制对象方法 var cloneObj = function (obj) { var newObj = {}; if (obj insta ...