题解报告:hdu 2844 & poj 1742 Coins(多重部分和问题)
2024-09-08 00:33:41
Problem Description
Whuacmers use coins.They have coins of value A1,A2,A3...An Silverland dollar. One day Hibix opened purse and found there were some coins. He decided to buy a very nice watch in a nearby shop. He wanted to pay the exact price(without change) and he known the price would not more than m.But he didn't know the exact price of the watch.
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.
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
The 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
For each test case output the answer on a single line.
Sample Input
3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0
Sample Output
8
4
解题思路:这题用二进制解法在poj却超时了,而杭电却不会(单调队列就别想了-->TLE);考虑多重部分和问题,时间复杂度是O(nW)。
hdu 2844 #AC代码(343ms):有坑,测试数据种W有为负数的,这就是一直RE的原因=_=...简单判断一下即可。
#include<algorithm>
#include<string.h>
#include<cstdio>
#include<iostream>
using namespace std;
int n,W,val[],cnt[],dp[];
int main(){
while(~scanf("%d%d",&n,&W)&&(n|W)){
for(int i=;i<=n;++i)scanf("%d",&val[i]);
for(int i=;i<=n;++i)scanf("%d",&cnt[i]);
if(W<=){puts("");continue;}
memset(dp,-,sizeof(dp));dp[]=;//注意初始化dp[0]为0
for(int i=;i<=n;++i){
for(int j=;j<=W;++j){
if(dp[j]>=)dp[j]=cnt[i];
else if(j<val[i]||dp[j-val[i]]<=)dp[j]=-;//面额太大或者或者在配更小的数时数量已经用光了
else dp[j]=dp[j-val[i]]-;
}
}
int ans=count_if(dp+,dp+W+,bind2nd(greater_equal<int>(),));//统计不小于0的个数
printf("%d\n",ans);
}
return ;
}
poj 1742 #AC代码(1813ms):中规中矩,W不会出现负数。
#include<algorithm>
#include<string.h>
#include<cstdio>
#include<iostream>
using namespace std;
int n,W,val[],cnt[],dp[];
int main(){
while(~scanf("%d%d",&n,&W)&&(n|W)){
memset(dp,-,sizeof(dp));dp[]=;
for(int i=;i<=n;++i)scanf("%d",&val[i]);
for(int i=;i<=n;++i)scanf("%d",&cnt[i]);
for(int i=;i<=n;++i){
for(int j=;j<=W;++j){
if(dp[j]>=)dp[j]=cnt[i];
else if(j<val[i]||dp[j-val[i]]<=)dp[j]=-;
else dp[j]=dp[j-val[i]]-;
}
}
int ans=count_if(dp+,dp+W+,bind2nd(greater_equal<int>(),));
printf("%d\n",ans);
}
return ;
}
最新文章
- html 绘制图像
- Htmlt_Div+Css简介
- Xcode-GitHub第三方库管理工具--CocoaPods
- matlab 全部的随机数函数
- JSP学习笔记(三):简单的Tomcat Web服务器
- ubuntu下安装xlrd模块,Mysqldb模块
- Windows 8实例教程系列 - 自定义应用风格
- 原生js轮播图
- elasticsearch 介绍
- lua 语言笔记
- redis for windows安装
- Codeforces Round #196 (Div. 2) A. Puzzles 水题
- sencha touch 扩展篇之使用sass自定义主题样式 (下)通过css修改官方组件样式以及自定义图标
- 445. Cosine Similarity【LintCode java】
- WCF引用方式之IIS方式寄宿服务
- Qt在VS(Visual Studio)中使用
- oracle 查看执行最慢 sql
- 《挑战程序设计竞赛》2.3 动态规划-基础 POJ3176 2229 2385 3616 3280
- HDU 5007 字符串匹配
- Centos6 使用yum快速搭建LAMP环境