POJ1285 Combinations, Once Again

题目地址

题解

用基本的背包处理即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
using namespace std;
typedef long long ll;
int read(){
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
int n[56],N,q,r;
ll f[56];
void packX(int d){
int p=1,_n,j;
for(j=N;j>=0;j--)
for(_n=1;_n<=min(n[d],j);_n++)
f[j]+=f[j-_n];
}
int main(){
int i,j,T=1;
for(;;T++){
memset(n,0,sizeof(n));
memset(f,0,sizeof(f));
scanf("%d%d",&N,&q);
if(!N&&!q)break;
for(i=0;i<N;i++)
scanf("%d",&j),
n[j-1]++;
for(f[0]=1ll,i=0;i<N;i++)
packX(i);
printf("Case %d:\n",T);
for(i=0;i<q;i++)
scanf("%d",&r),
printf("%lld\n",f[r]);
}
return 0;
}