陈俊屹
(陈俊屹)
1
题目描述
有n种面值的硬币A1,A2…An, 每种硬币有C1,C2…Cn个
求他们一共可以组合成多少种1−m之间面值
输入格式
第一行输入两个整数n,m
第二行输入2∗n个整数，A1,A2…An,C1,C2…Cn
输出格式
输出一个整数
样例
Input 1
3 10 1 2 4 2 1 1
Output 1
8
数据范围
1<=n<=100,1<=m<=105
1<=Ai<=105,1<=Ci<=1000
样例解释
样例解释：
硬币面值为1,2,4，数量分别为2,1,1
可以组成的面值为1,2,4,3,5,6,7,8共8种
我哪里错了 
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int a[N],dp[N];
int main(){
int n,m;
scanf(“%d”,&n);
for(int i=1;i<=n;i++){
scanf(“%d”,&a[i]);
m+=a[i];
}dp[0]=1;
for(int i=1;i<=n;i++){
for(int j=m;j>=a[i];j–){
if(dp[j-a[i]]==1) dp[j]=1;
}
}int ret=0;
for(int i=1;i<=m;i++){
ret+=dp[i];
}printf(“%d”,ret);
return 0;
}
2 个赞
方悦丞
(初音ミク)
2
选中你的代码
再点击</>
可以格式化你的代码
让你的代码更美观
3 个赞
方悦丞
(初音ミク)
3
思路：
这是简单的完全背包。
但是计算一下
传统的完全背包无法通过时间复杂度，
所以我们增加优化：
如果状态dp[j]已经可以被满足则不再枚举，直接进行下一个状态
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,dp[1000050],book[1000050];
struct edge
{
int a,c;
}p[1050];
signed main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)scanf("%lld",&p[i].a);
for(int i=1;i<=n;i++)scanf("%lld",&p[i].c);
dp[0]=1;
book[0]=1;
for(int i=1;i<=n;i++)
{
for(int j=m;j>=1;j--)
{
if(book[j])continue;
for(int k=1;k*p[i].a<=j&&k<=p[i].c;k++)
{
dp[j]|=dp[j-k*p[i].a];
if(dp[j])book[j]=1;
}
}
}
int ans=0;
for(int i=1;i<=m;i++)
if(dp[i])++ans;
printf("%lld",ans);
return 0;
}
至少样例过力（喜
3 个赞
