C - Coin Change (III)(多重背包 二进制优化)
Time Limit:2000MS Memory Limit:32768KB 64bit IO Format:%lld & %llu
Description
In a strange shop there are n types of coins of value A1, A2 ... An. C1, C2, ... Cn denote the number of coins of value A1, A2 ... Anrespectively. You have to find the number of different values (from 1 to m), which can be produced using these coins.
Input
Input starts with an integer T (≤ 20), denoting the number of test cases.
Each case starts with a line containing two integers n (1 ≤ n ≤ 100), m (0 ≤ m ≤ 105). The next line contains 2n integers, denoting A1, A2... An, C1, C2 ... Cn (1 ≤ Ai ≤ 105, 1 ≤ Ci ≤ 1000). All Ai will be distinct.
Output
For each case, print the case number and the result.
Sample Input
2
3 10
1 2 4 2 1 1
2 5
1 4 2 1
Sample Output
Case 1: 8
Case 2: 4
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define mod 100000007
int a[],c[],dp[],b[];
int main()
{
int n,k,t,i,j,r;
scanf("%d",&t);
for(i=; i<=t; i++)
{
memset(dp,,sizeof(dp));
scanf("%d%d",&n,&k);
for(j=; j<=n; j++)scanf("%d",&b[j]);
for(j=; j<=n; j++)scanf("%d",&c[j]);
int nu=,re,rs;
for(j=; j<=n; j++)
{
re=b[j],rs=c[j];
c[j]*=b[j];
while(rs)
{
if(re<c[j])
a[nu++]=re,c[j]-=re;
else a[nu++]=c[j];
rs>>=;
re<<=;
}
}
for(j=; j<nu; j++)
{
for(r=k; r>=; r--)
{
if(dp[r]&&r+a[j]<=k)
dp[r+a[j]]=;
if(r==&&a[j]<=k)
dp[a[j]]=;
} }
int sum=;
for(r=; r<=k; r++)sum+=dp[r];
cout<<"Case "<<i<<": ";
cout<<sum<<endl;
} }
最新文章
- System.Drawing.Image在Save之后Type变了
- ext4 文件系统的一些记录
- 【Hibernate 7】浅谈Hibernate的缓存机制
- 详解 MySQL 中的 explain
- WPF——菜单栏及TabControl
- C#微信公众号——本地调试
- Linux(Ubuntu)使用日记------markdown文档转化为word文档
- C++STL模板库序列容器之List容器
- Linux查看系统信息的命令及已安装软件包的命令
- 洛谷P1966 【火柴排队】
- TextView文字描边实现
- <;crtdbg.h>; 的作用
- java的myeclipse,java页面改动默认的javadoc方法
- HTML标签嵌套规则
- HDU 5873 Football Games(竞赛图兰道定理)
- Ehcache配置参数简介
- netstat-ll-grep-nohup-df-supervisord
- Bash to check SSL cert expired
- 基于CSS3 3D百叶窗图像过渡特效
- kettle的日志