USACO:Money System
772 ワード
/*
ID: Jang Lawrence
PROG: money
LANG: C++
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#define mp make_pair
using namespace std;
typedef long long lng;
lng dp[26][10001];
int n,sum;
int a[30];
int main()
{
#ifndef DEBUG
freopen("money.in","r",stdin);
freopen("money.out","w",stdout);
#endif
dp[0][0]=1;
scanf("%d%d",&n,&sum);
for(int i=1;i<=n;++i)
scanf("%d",a+i);
for(int i=1;i<=n;++i)
for(int j=0;j<=sum;j++)
{
int k=j;
while(k>=0)
{
dp[i][j]+=dp[i-1][k];
k-=a[i];
}
}
printf("%lld
",dp[n][sum]);
return 0;
}