【USACO 2-3-4】通貨システムdp
520 ワード
原題
//usaco2-3-4 Money Systems
#include
#include
#include
#define ll long long
ll c[101000],dp[101000];
int n,v;
int main()
{
scanf("%d%d",&v,&n);
for (int i=1;i<=v;i++) scanf("%lld",&c[i]);
memset(dp,0,sizeof(dp));
dp[0]=1;
for (int j=1;j<=v;j++)
for (int i=1;i<=n;i++)
if (i>=c[j]) dp[i]+=dp[i-c[j]];
printf("%lld
",dp[n]);
return 0;
}