杭電1085

ここにリンクの内容を書きます
Holding Bin-Laden Captive! Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 13861 Accepted Submission(s): 6230
Problem Description We all know that Bin-Laden is a notorious terrorist, and he has disappeared for a long time. But recently, it is reported that he hides in Hang Zhou of China! “Oh, God! How terrible! ”
Don’t be so afraid, guys. Although he hides in a cave of Hang Zhou, he dares not to go out. Laden is so bored recent years that he fling himself into some math problems, and he said that if anyone can solve his problem, he will give himself up! Ha-ha! Obviously, Laden is too proud of his intelligence! But, what is his problem? 「Given some Chinese Coins(コイン)」(three kinds–1,2,5)、andtheir number is num_1,num_2 and num_5 respectively,please output the minimum value that you cannot pay with given coins.」You,super ACMer,should solve the problem easily,and don’t forget to take$25000,000 from Bush!
Input
Output Output the minimum positive value that one cannot pay with given coins, one line for one case.
Sample Input 1 1 3 0 0 0
Sample Output 4
标题:与えられた三中硬貨、額面はそれぞれ1,2,5、与えられた三種類の硬貨の数はそれぞれnum_1,num_2,num_5.次に、これらの硬貨が構成できない最小の額面がいくらであるかを解く.例えば、与えられた例では、額面が1の硬貨が1枚、額面が2の硬貨が1枚、額面が5の硬貨が3枚であると、構成できる額面が1,2,3,5......であるため、構成できない最小の額面は4である.これが母関数の問題ですが、ここでは組合せ数を求めるわけではありませんので、int行の配列で組合せ数を記録する必要はありません.trueとfalseでその値を表すことができるかどうかを示すだけでいいです.もちろんintで組み合わせ数を記録してもいいのですが、組み合わせ量が非常に大きいので、オーバーフローに注意して、試してみてもいいですが、0より大きいと判断したときは1を置いておけば大丈夫です.
コード:

# include <iostream>
# include <cstring>
using namespace std;

int main(){

    int n,i,j,k,m;
    int money[9];//      
    int c1[10000],c2[10000];

    while(cin>>money[1]>>money[2]>>money[5]&&money[1]||money[2]||money[5]){
        //     
        memset(c1,0,sizeof(c1));
        memset(c2,0,sizeof(c2));

        m = money[1]*1+money[2]*2+money[5]*5;//          
        for(i=0;i<=money[1];i++){//       
            c1[i] = 1; 
        } 

        for(i=2;i<=5;i+=3){//          
            for(j=0;j<=m;j++){// m       , 
                for(k=0;k+j<=m&&k/i<=money[i];k+=i){ //  k=i*money[i]; k  2 5     
                    c2[k+j]+= c1[j]; 
                }
            }

            for(k=0;k<=m;k++){
                c1[k] = c2[k];
                c2[k] = 0;
            }
        }

        for(i=1;i<=m;i++){
            if(!c1[i]){
                break;
            }
        }

        cout<<i<<endl;
    }


}

方法2:

# include <iostream>
using namespace std;

int main()
{
    int a,b,c;
    while(cin>>a>>b>>c)
    {
        if(a==0&&b==0&c==0)
        break;
        if(a==0)
        printf("1
");
        else if(a+2*b<4)//a>=1，b   0 
        printf("%d
",a+2*b+1);
        else//a!=0&&b1!=0 c    
        printf("%d
",a+2*b+5*c+1);
    }
    return 0;
}

  3:

 # include <iostream>
 # include <cstring>
 using namespace std;

 # define MAX 10000 
 int c1[MAX],c2[MAX];
 int num[4];
 int main(){

    while(cin>>num[1]>>num[2]>>num[3]&&num[1]||num[2]||num[3]){

        int max_ = num[1]*1 + num[2]*2 + num[3]*5;
        int i,j,k;
        memset(c1,0,sizeof(c1));
        memset(c2,0,sizeof(c2));

        for(i=0;i<=num[1];i++){//        
            c1[i] = 1;
        }

        //   for                        
        for(i=0;i<=num[1];i++){//      
            for(j=0;j<=num[2]*2;j+=2){//      
                c2[i+j] += c1[i];// c2[i+j]-->         c1[i]-->   ax^n  a，    
            }
        } 

            /*
             for            j<=num[1]*1+num[2]*2
                       for      x^a x^b  ==x^(a+b)      num[1]*1+num[2]*2 
            */ 
            for(j=0;j<=num[1]*1+num[2]*2;j++){

                c1[j] = c2[j];
                c2[j] = 0;
            }   



        for(i=0;i<=num[1]*1+num[2]*2;i++){
            for(j=0;j<=num[3]*5;j+=5){
                c2[j+i] += c1[i];
            }
        } 
        for(j=0;j<=num[1]*1+num[2]*2+num[3]*5;j++){

                c1[j] = c2[j];
                c2[j] = 0;
        }   

        for(j=0;j<=max_;j++){
            if(c1[j]==0){
                break;
            }
        }

        cout<<j<<endl;


    }


    return 0;
 }

Runtime Error(ACCESS_VIOLATION)