【USACO 2-3-4】通貨システムdp


原題
//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; }