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输入 #13 10 1 2 4 2 1 1 2 5 1 4 2 1 0 0输出 #18 4C实现#includebits/stdc.husingnamespacestd;intn,m,a[105],c[105];booldp[100005];signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);while(cinnm){if(!n!m)break;for(inti1;in;i)cina[i];for(inti1;in;i)cinc[i];memset(dp,0,sizeofdp);dp[0]1;for(inti1;in;i){for(intj1;jc[i];j*2){intsmin(j,c[i]);c[i]-s;for(intkm;ks*a[i];k--)if(dp[k-s*a[i]])dp[k]1;}if(c[i]){for(intjm;jc[i]*a[i];j--){if(dp[j-c[i]*a[i]]){dp[j]1;}}}}intans0;for(inti1;im;i){ansdp[i];}coutans\n;}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容