自动搬运

查看原文

来自洛谷，原作者为

	dengyaotriangle 我弱弱 您强强 嘤嘤嘤

搬运于2025-08-24 21:25:29，当前版本为作者最后更新于2018-06-03 11:21:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看没有写C++短代码题解的就来一发~

这题就是一个完全背包问题

dp方程 x(i)=sum(x(i-h(j)) 边界x(0)=1

其中x(i)代表凑成i元有x(i)种方法，h(j)代表第j个货币的面值

#include<bits/stdc++.h>
long long v,n,h[30],dp[10005]={1};
int main(){
	std::cin>>v>>n;
	for(int i=0;i<v;i++) std::cin>>h[i];
	for(int i=0;i<v;i++)for(int j=h[i];j<=n;j++) dp[j]+=dp[j-h[i]];
	std::cout<<dp[n];
    return 0;
}