裸$01$背包。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define ll long long
#define gc getchar()
using namespace std;
const int N=105,M=1e4+5;
inline void qr(int &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
void qw(int x)
{
if(x<0)x=-x,putchar('-');
if(x/10)qw(x/10);
putchar(x%10+48);
}
ll f[M];int a[N];
int main()
{
int n,m;qr(n);qr(m);
for(int i=1;i<=n;i++)qr(a[i]);
f[0]=1;
for(int i=1;i<=n;i++)
for(int j=m;j>=a[i];j--)
f[j]+=f[j-a[i]];
qw(f[m]);puts("");
return 0;
}
最后一次更新于2019-10-17
0 条评论