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; }