P2089 烤鸡

Description

原题地址：P2089 烤鸡 - 洛谷

思路：可直接暴力枚举，或者用深度优先搜索

实现

枚举

只需要做两层嵌套循环即可：

// 枚举题解
#include<iostream>  
using namespace std;  
int main()  
{  
    int a,b,c,d,e,f,g,h,i,j,in,x=0;  
    cin>>in;  
    for (a=1;a<=3;a++){  
        for (b=1;b<=3;b++){  
            for (c=1;c<=3;c++){  
                for (d=1;d<=3;d++){  
                    for (e=1;e<=3;e++){  
                        for (f=1;f<=3;f++){  
                            for (g=1;g<=3;g++){  
                                for(h=1;h<=3;h++){  
                                    for (i=1;i<=3;i++){  
                                        for (j=1;j<=3;j++){  
                                            if (a+b+c+d+e+f+g+h+i+j==in) x++;   
                                        }  
                                    }  
                                }  
                            }  
                        }  
                    }  
                }  
            }  
        }  
    }  
    cout<<x<<endl;  
    for (a=1;a<=3;a++){  
        for (b=1;b<=3;b++){  
            for (c=1;c<=3;c++){  
                for (d=1;d<=3;d++){  
                    for (e=1;e<=3;e++){  
                        for (f=1;f<=3;f++){  
                            for (g=1;g<=3;g++){  
                                for(h=1;h<=3;h++){  
                                    for (i=1;i<=3;i++){  
                                        for (j=1;j<=3;j++){  
                                            if (a+b+c+d+e+f+g+h+i+j==in){  
                                                cout<<a<<" ";  
                                                cout<<b<<" ";  
                                                cout<<c<<" ";  
                                                cout<<d<<" ";  
                                                cout<<e<<" ";  
                                                cout<<f<<" ";  
                                                cout<<g<<" ";  
                                                cout<<h<<" ";  
                                                cout<<i<<" ";  
                                                cout<<j<<endl;  
                                            }  
                                        }  
                                    }  
                                }  
                            }  
                        }  
                    }  
                }  
            }  
        }  
    }  
}

深度优先搜索

大致的思路也是需要枚举一下(?)然后进行搜索

#include<bits/stdc++.h>
using namespace std;
int a,n[11];
int ans; // 存储答案

void print_ans(){ // 输出10个配料的克数的函数
    for(int i=1;i<=10;++i){
        printf("%d",a[i]);
    }
    printf("\n");
    return;
}

void print_method(int cnt, int step){ // 打印方案的函数，cnt表示当前美味程度，step表示放了几种配料
    if(cnt<0) return; // 如果美味程度为负数直接停止
    if(step==10&&cnt!=0) return; //如果放完配料后cnt还有剩余也停止
    if(step==10&&cnt==0){ // 若放完配料后cnt无剩余直接输出配料方案
        print_ans();
        return;
    }
    for(int i=1;i<=3;i++){
        a[step+1]=i; // 枚举出下一次配料加多少克
        print_method(cnt-i, step+1); // 搜索开始
    }
}

void count_ans(int cnt, int step){ // 计算答案函数
    if(cnt<0) return;
    if(step==10&&cnt!=0) return;
    if(step==10&&cnt==0){
        ans++;
        return;
    }
    for(int i=1;i<=3;++i){
        a[step+1]=i;
        count_ans(cnt-i, step+1);
    }
}

int main(){
    scanf("%d",&n);
    if(n>30){ // cnt最大值为3，十个值加起来就是30
        printf("0");
        return 0;
    }
    count_ans(n,0); // 统计答案数
    printf("%d\n", ans);
    print_method(n,0);
    return 0;
}