COJ 0557 4013多重部分和问题

4013多重部分和问题

难度级别：B；运行时间限制：2000ms；运行空间限制：262144KB；代码长度限制：2000000B

试题描述

n种大小不同的数字 Ai，每种各Mi个，判断是否可以从这些数字之中选出若干个使他们的和恰好为K。

输入

第一行为两个正整数n,K。
第二行为n个数Ai，以空格隔开。
第三行为n个数Mi，以空格隔开。

输出

若可行则输出"yes"
否则输出"no"

输入示例

3 17
3 5 8
3 2 2

输出示例

yes

其他说明

1<=n<=100
1<=K<=50000
1<=Ai<=40
1<=Mi<=50

若数字相同对程序并无影响。

题解：此题有四个层次：

1.枚举bool乱搞：

 1 //标程4
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<queue>
 7 #include<cstring>
 8 #define PAU putchar(' ')
 9 #define ENT putchar('
')
10 using namespace std;
11 const int maxn=100+10,maxm=50000+10,inf=-1u>>1;
12 bool d[maxn][maxm];int n,tar,A[maxn],num[maxn];
13 inline int read(){
14     int x=0,sig=1;char ch=getchar();
15     while(!isdigit(ch)){if(ch=='-') sig=-1;ch=getchar();}
16     while(isdigit(ch)) x=10*x+ch-'0',ch=getchar();
17     return x*=sig;
18 }
19 inline void write(int x){
20     if(x==0){putchar('0');return;}if(x<0) putchar('-'),x=-x;
21     int len=0,buf[15];while(x) buf[len++]=x%10,x/=10;
22     for(int i=len-1;i>=0;i--) putchar(buf[i]+'0');return;
23 }
24 void init(){
25     memset(d,false,sizeof(d));
26     n=read();tar=read();
27     for(int i=0;i<n;i++) A[i]=read();
28     for(int i=0;i<n;i++) num[i]=read();
29     return;
30 }
31 void work(){
32     d[0][0]=true;
33     for(int i=0;i<n;i++)
34         for(int j=0;j<=tar;j++)
35             for(int k=0;k<=num[i]&&k*A[i]<=j;k++)
36                 d[i+1][j]|=d[i][j-k*A[i]];
37     if(d[n][tar]) puts("yes");
38     else puts("no");
39     return;
40 }
41 void print(){
42     return;
43 }
44 int main(){
45     init();work();print();return 0;
46 }

2.快看窝萌还可以滚动，好神奇！

 1 //标程3
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<queue>
 7 #include<cstring>
 8 #define PAU putchar(' ')
 9 #define ENT putchar('
')
10 using namespace std;
11 const int maxn=100+10,maxm=50000+10,inf=-1u>>1;
12 bool d[2][maxm];int n,tar,A[maxn],num[maxn];
13 inline int read(){
14     int x=0,sig=1;char ch=getchar();
15     while(!isdigit(ch)){if(ch=='-') sig=-1;ch=getchar();}
16     while(isdigit(ch)) x=10*x+ch-'0',ch=getchar();
17     return x*=sig;
18 }
19 inline void write(int x){
20     if(x==0){putchar('0');return;}if(x<0) putchar('-'),x=-x;
21     int len=0,buf[15];while(x) buf[len++]=x%10,x/=10;
22     for(int i=len-1;i>=0;i--) putchar(buf[i]+'0');return;
23 }
24 void init(){
25     memset(d,false,sizeof(d));
26     n=read();tar=read();
27     for(int i=0;i<n;i++) A[i]=read();
28     for(int i=0;i<n;i++) num[i]=read();
29     return;
30 }
31 void work(){
32     int tc=0;d[tc][0]=true;
33     for(int i=0;i<n;i++){
34         tc^=1;
35         for(int j=0;j<=tar;j++)
36             for(int k=0;k<=num[i]&&k*A[i]<=j;k++)
37                 d[tc][j]|=d[tc^1][j-k*A[i]];
38     }
39     if(d[tc][tar]) puts("yes");
40     else puts("no");
41     return;
42 }
43 void print(){
44     return;
45 }
46 int main(){
47     init();work();print();return 0;
48 }

3.窝萌还可以搞出正好凑成k的：

 1 //标程2 
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<queue>
 7 #include<cstring>
 8 #define PAU putchar(' ')
 9 #define ENT putchar('
')
10 using namespace std;
11 const int maxn=100+10,maxm=50000+10,inf=-1u>>1;
12 int d[2][maxm],n,tar,A[maxn],num[maxn];
13 inline int read(){
14     int x=0,sig=1;char ch=getchar();
15     while(!isdigit(ch)){if(ch=='-') sig=-1;ch=getchar();}
16     while(isdigit(ch)) x=10*x+ch-'0',ch=getchar();
17     return x*=sig;
18 }
19 inline void write(int x){
20     if(x==0){putchar('0');return;}if(x<0) putchar('-'),x=-x;
21     int len=0,buf[15];while(x) buf[len++]=x%10,x/=10;
22     for(int i=len-1;i>=0;i--) putchar(buf[i]+'0');return;
23 }
24 void init(){
25     memset(d,-1,sizeof(d));
26     n=read();tar=read();
27     for(int i=0;i<n;i++) A[i]=read();
28     for(int i=0;i<n;i++) num[i]=read();
29     return;
30 }
31 void work(){
32     int tc=0;d[tc][0]=0;
33     for(int i=0;i<n;i++){
34         tc^=1;
35         for(int j=0;j<=tar;j++){
36             if(d[tc^1][j]>=0) d[tc][j]=num[i];
37             else if((j>=A[i]&&d[tc][j-A[i]]>=0)&&d[tc^1][j]) d[tc][j]=d[tc][j-A[i]]-1;
38             else d[tc][j]=-1;
39         }
40     }
41     if(d[tc][tar]>=0) puts("yes");
42     else puts("no");
43     return;
44 }
45 void print(){
46     return;
47 }
48 int main(){
49     init();work();print();return 0;
50 }

4.快看窝萌还可以滚动，好神奇！

 1 //标程1
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<queue>
 7 #include<cstring>
 8 #define PAU putchar(' ')
 9 #define ENT putchar('
')
10 using namespace std;
11 const int maxn=100+10,maxm=50000+10,inf=-1u>>1;
12 int d[maxm],n,tar,A[maxn],num[maxn];
13 inline int read(){
14     int x=0,sig=1;char ch=getchar();
15     while(!isdigit(ch)){if(ch=='-') sig=-1;ch=getchar();}
16     while(isdigit(ch)) x=10*x+ch-'0',ch=getchar();
17     return x*=sig;
18 }
19 inline void write(int x){
20     if(x==0){putchar('0');return;}if(x<0) putchar('-'),x=-x;
21     int len=0,buf[15];while(x) buf[len++]=x%10,x/=10;
22     for(int i=len-1;i>=0;i--) putchar(buf[i]+'0');return;
23 }
24 void init(){
25     memset(d,-1,sizeof(d));
26     n=read();tar=read();
27     for(int i=0;i<n;i++) A[i]=read();
28     for(int i=0;i<n;i++) num[i]=read();
29     return;
30     return;
31 }
32 void work(){
33     d[0]=0;
34     for(int i=0;i<n;i++){
35         for(int j=0;j<=tar;j++){
36             if(d[j]>=0) d[j]=num[i];
37             else if((j>=A[i]&&d[j-A[i]]>=0)&&d[j]) d[j]=d[j-A[i]]-1;
38             else d[j]=-1;
39         }
40     }
41     if(d[tar]>=0) puts("yes");
42     else puts("no");
43     return;
44 }
45 void print(){
46     return;
47 }
48 int main(){
49     init();work();print();return 0;
50 }

结论：然并卵。