企业官网建设流程全解析

P10973 Coins

题目描述

银国的人们使用硬币。他们有面值分别为A1,A2,A3,…,AnA_1, A_2, A_3, \dots, A_nA1​,A2​,A3​,…,An​的硬币。有一天，托尼打开了他的储蓄罐，发现里面有一些硬币。他决定去附近的商店购买一块非常漂亮的手表。他想要支付准确的价格（不找零），而他知道手表的价格不会超过mmm。但他不知道手表的确切价格。

你需要编写一个程序，读取nnn、mmm、A1,A2,A3,…,AnA_1, A_2, A_3, \dots, A_nA1​,A2​,A3​,…,An​以及对应的数量C1,C2,C3,…,CnC_1, C_2, C_3, \dots, C_nC1​,C2​,C3​,…,Cn​（表示托尼拥有的每种面值的硬币数量），然后计算托尼可以用这些硬币支付的价格数量（从 1 到mmm的所有价格）。

输入格式

输入包含多个测试用例（不超过252525组）。每个测试用例的第一行包含两个整数n(1≤n≤100)n (1 ≤ n ≤ 100)n(1≤n≤100)和m(m≤100000)m (m ≤ 100000)m(m≤100000)。第二行包含2n2n2n个整数，分别表示A1,A2,A3,…,AnA_1, A_2, A_3, \dots, A_nA1​,A2​,A3​,…,An​和C1,C2,C3,…,Cn(1≤Ai≤100000,1≤Ci≤1000)C_1, C_2, C_3, \dots, C_n (1 ≤ A_i ≤ 100000, 1 ≤ C_i ≤ 1000)C1​,C2​,C3​,…,Cn​(1≤Ai​≤100000,1≤Ci​≤1000)。最后一个测试用例以两个零结尾。

输出格式

对于每个测试用例，在单独的一行输出答案。

输入输出样例 #1

输入 #1

3 10 1 2 4 2 1 1 2 5 1 4 2 1 0 0

输出 #1

8 4

C++实现

#include<bits/stdc++.h>usingnamespacestd;intn,m,a[105],c[105];booldp[100005];signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);while(cin>>n>>m){if(!n&&!m)break;for(inti=1;i<=n;i++)cin>>a[i];for(inti=1;i<=n;i++)cin>>c[i];memset(dp,0,sizeofdp);dp[0]=1;for(inti=1;i<=n;i++){for(intj=1;j<=c[i];j*=2){ints=min(j,c[i]);c[i]-=s;for(intk=m;k>=s*a[i];k--)if(dp[k-s*a[i]])dp[k]=1;}if(c[i]){for(intj=m;j>=c[i]*a[i];j--){if(dp[j-c[i]*a[i]]){dp[j]=1;}}}}intans=0;for(inti=1;i<=m;i++){ans+=dp[i];}cout<<ans<<'\n';}return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容