COJ 0557 4013多重部分和问题

时间：2023-11-17 09:24:38
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 ;

 }

结论：然并卵。

相关文章