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乱搞：

 //标程4
 #include<iostream>
 #include<cstdio>
 #include<cmath>
 #include<algorithm>
 #include<queue>
 #include<cstring>
 #define PAU putchar(' ')
 #define ENT putchar('\n')
 using namespace std;
 const int maxn=+,maxm=+,inf=-1u>>;
 bool d[maxn][maxm];int n,tar,A[maxn],num[maxn];
 inline int read(){
     int x=,sig=;char ch=getchar();
     while(!isdigit(ch)){if(ch=='-') sig=-;ch=getchar();}
     while(isdigit(ch)) x=*x+ch-'',ch=getchar();
     return x*=sig;
 }
 inline void write(int x){
     if(x==){putchar('');return;}if(x<) putchar('-'),x=-x;
     int len=,buf[];while(x) buf[len++]=x%,x/=;
     for(int i=len-;i>=;i--) putchar(buf[i]+'');return;
 }
 void init(){
     memset(d,false,sizeof(d));
     n=read();tar=read();
     for(int i=;i<n;i++) A[i]=read();
     for(int i=;i<n;i++) num[i]=read();
     return;
 }
 void work(){
     d[][]=true;
     for(int i=;i<n;i++)
         for(int j=;j<=tar;j++)
             for(int k=;k<=num[i]&&k*A[i]<=j;k++)
                 d[i+][j]|=d[i][j-k*A[i]];
     if(d[n][tar]) puts("yes");
     else puts("no");
     return;
 }
 void print(){
     return;
 }
 int main(){
     init();work();print();return ;
 }

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

 //标程3
 #include<iostream>
 #include<cstdio>
 #include<cmath>
 #include<algorithm>
 #include<queue>
 #include<cstring>
 #define PAU putchar(' ')
 #define ENT putchar('\n')
 using namespace std;
 const int maxn=+,maxm=+,inf=-1u>>;
 bool d[][maxm];int n,tar,A[maxn],num[maxn];
 inline int read(){
     int x=,sig=;char ch=getchar();
     while(!isdigit(ch)){if(ch=='-') sig=-;ch=getchar();}
     while(isdigit(ch)) x=*x+ch-'',ch=getchar();
     return x*=sig;
 }
 inline void write(int x){
     if(x==){putchar('');return;}if(x<) putchar('-'),x=-x;
     int len=,buf[];while(x) buf[len++]=x%,x/=;
     for(int i=len-;i>=;i--) putchar(buf[i]+'');return;
 }
 void init(){
     memset(d,false,sizeof(d));
     n=read();tar=read();
     for(int i=;i<n;i++) A[i]=read();
     for(int i=;i<n;i++) num[i]=read();
     return;
 }
 void work(){
     int tc=;d[tc][]=true;
     for(int i=;i<n;i++){
         tc^=;
         for(int j=;j<=tar;j++)
             for(int k=;k<=num[i]&&k*A[i]<=j;k++)
                 d[tc][j]|=d[tc^][j-k*A[i]];
     }
     if(d[tc][tar]) puts("yes");
     else puts("no");
     return;
 }
 void print(){
     return;
 }
 int main(){
     init();work();print();return ;
 }

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

 //标程2
 #include<iostream>
 #include<cstdio>
 #include<cmath>
 #include<algorithm>
 #include<queue>
 #include<cstring>
 #define PAU putchar(' ')
 #define ENT putchar('\n')
 using namespace std;
 const int maxn=+,maxm=+,inf=-1u>>;
 int d[][maxm],n,tar,A[maxn],num[maxn];
 inline int read(){
     int x=,sig=;char ch=getchar();
     while(!isdigit(ch)){if(ch=='-') sig=-;ch=getchar();}
     while(isdigit(ch)) x=*x+ch-'',ch=getchar();
     return x*=sig;
 }
 inline void write(int x){
     if(x==){putchar('');return;}if(x<) putchar('-'),x=-x;
     int len=,buf[];while(x) buf[len++]=x%,x/=;
     for(int i=len-;i>=;i--) putchar(buf[i]+'');return;
 }
 void init(){
     memset(d,-,sizeof(d));
     n=read();tar=read();
     for(int i=;i<n;i++) A[i]=read();
     for(int i=;i<n;i++) num[i]=read();
     return;
 }
 void work(){
     int tc=;d[tc][]=;
     for(int i=;i<n;i++){
         tc^=;
         for(int j=;j<=tar;j++){
             if(d[tc^][j]>=) d[tc][j]=num[i];
             else if((j>=A[i]&&d[tc][j-A[i]]>=)&&d[tc^][j]) d[tc][j]=d[tc][j-A[i]]-;
             else d[tc][j]=-;
         }
     }
     if(d[tc][tar]>=) puts("yes");
     else puts("no");
     return;
 }
 void print(){
     return;
 }
 int main(){
     init();work();print();return ;
 }

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

 //标程1
 #include<iostream>
 #include<cstdio>
 #include<cmath>
 #include<algorithm>
 #include<queue>
 #include<cstring>
 #define PAU putchar(' ')
 #define ENT putchar('\n')
 using namespace std;
 const int maxn=+,maxm=+,inf=-1u>>;
 int d[maxm],n,tar,A[maxn],num[maxn];
 inline int read(){
     int x=,sig=;char ch=getchar();
     while(!isdigit(ch)){if(ch=='-') sig=-;ch=getchar();}
     while(isdigit(ch)) x=*x+ch-'',ch=getchar();
     return x*=sig;
 }
 inline void write(int x){
     if(x==){putchar('');return;}if(x<) putchar('-'),x=-x;
     int len=,buf[];while(x) buf[len++]=x%,x/=;
     for(int i=len-;i>=;i--) putchar(buf[i]+'');return;
 }
 void init(){
     memset(d,-,sizeof(d));
     n=read();tar=read();
     for(int i=;i<n;i++) A[i]=read();
     for(int i=;i<n;i++) num[i]=read();
     return;
     return;
 }
 void work(){
     d[]=;
     for(int i=;i<n;i++){
         for(int j=;j<=tar;j++){
             if(d[j]>=) d[j]=num[i];
             else if((j>=A[i]&&d[j-A[i]]>=)&&d[j]) d[j]=d[j-A[i]]-;
             else d[j]=-;
         }
     }
     if(d[tar]>=) puts("yes");
     else puts("no");
     return;
 }
 void print(){
     return;
 }
 int main(){
     init();work();print();return ;
 }

结论：然并卵。