P2089 烤鸡

1.题目描述P2089

猪猪 Hanke 特别喜欢吃烤鸡（本是同畜牲，相煎何太急！）Hanke 吃鸡很特别，为什么特别呢？因为他有100种配料（芥末、孜然等），每种配料可以放1到3克，任意烤鸡的美味程度为所有配料质量之和。现在Hanke 想要知道，如果给你一个美味程度n，请输出这10种配料的所有搭配方案。

输入格式

一个正整数n，表示美味程度。

输出格式

第一行，方案总数。
第二行至结束，10个数，表示每种配料所放的质量，按字典序排列。
如果没有符合要求的方法，就只要在第一行输出一个0。

输入输出样例

输入：

11

输出：

10
1 1 1 1 1 1 1 1 1 2
1 1 1 1 1 1 1 1 2 1
1 1 1 1 1 1 1 2 1 1
1 1 1 1 1 1 2 1 1 1
1 1 1 1 1 2 1 1 1 1
1 1 1 1 2 1 1 1 1 1
1 1 1 2 1 1 1 1 1 1
1 1 2 1 1 1 1 1 1 1
1 2 1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1 1

2.实现方法

??这题难点主要就是如何枚举所有符合的情况，题目中有要求按字典序排列且配料数固定为10，配料质量范围为1到3，从这些提示（特别是按字典序排列）中得到,我们可以用最简单粗暴的方法，用十重循环来枚举，当相加与n相等时就输出。（用循环首先满足条件输出的肯定是字典序较小的）

#include<stdio.h>
int main(){
    int n;
    scanf("%d",&n);
    if(n>30||n<10) printf("0");
    else{
        int sum=0;
        for(int a=1;a<4;a++)
            for(int b=1;b<4;b++)
                for(int c=1;c<4;c++)
                    for(int d=1;d<4;d++)
                        for(int e=1;e<4;e++)
                            for(int f=1;f<4;f++)
                                for(int g=1;g<4;g++)
                                    for(int h=1;h<4;h++)
                                        for(int i=1;i<4;i++)
                                            for(int j=1;j<4;j++){
                                                if(a+b+c+d+e+f+g+h+i+j==n){
                                                    sum++;
                                                }
                                            }
        printf("%d\n",sum);
        for(int a=1;a<4;a++)
            for(int b=1;b<4;b++)
                for(int c=1;c<4;c++)
                    for(int d=1;d<4;d++)
                        for(int e=1;e<4;e++)
                            for(int f=1;f<4;f++)
                                for(int g=1;g<4;g++)
                                    for(int h=1;h<4;h++)
                                        for(int i=1;i<4;i++)
                                            for(int j=1;j<4;j++){
                                                if(a+b+c+d+e+f+g+h+i+j==n){
                                                    printf("%d %d %d %d %d %d %d %d %d %d\n",i,j,l,t,r,a,b,c,d,e);
                                                }                                       
                                            }
    }
    return 0;
}

pow（3,10）次循环，暴力但有效??

3.思路总结

如果题目要求输出按字典序排列并且输出变量个数固定且范围不大，可考虑多重循环解决

P1618 三连击（升级版）

1.题目描述P1618

题目易错点：（1）三个三位数的比例是A:B:C （2）按照每行第一个数字升序排列

2.实现方法

??该题在实现上根据题意进行模拟即可，就是先选出一个三位数然后在判断是否符合各种条件，符合即输出。
该题主要的坑点在与是否正确理解比例为A:B:C,这个比例不一定是最简,所以在枚举数做判断之前，应该先将比例化到最简，这样才不会漏解（按最简比算对数才是最多的）。

#include<stdio.h>
int judge(int a[]){
    int c[9],count=0,temp;
    for(int i=0;i<3;i++){
        c[count]=a[i]/100;
        c[count+1]=a[i]/10%10;
        c[count+2]=a[i]%10;
        count+=3;
    }
    for(int i=0;i<8;i++){
        for(int j=0;j<8;j++){
            if(c[j]>c[j+1]){
                temp=c[j];
                c[j]=c[j+1];
                c[j+1]=temp;
            }
        }
    }
    int k=1;
    for(int i=0;i<8;i++){
        if(c[i]==c[i+1]||c[i]==0) k=0;
    } 
    if(k==1) return 1;
    else return 0;
}
int main(){
    double b[3],temp,sum;
    scanf("%lf %lf %lf",&b[0],&b[1],&b[2]);
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            if(b[j]>b[j+1]){
                temp=b[j];
                b[j]=b[j+1];
                b[j+1]=temp;
            }
        }
    }
    b[1]/=b[0];b[2]/=b[0];b[0]=1;
    int a[3],ans,k=1;
    for(int i=1;i<=9;i++){
        for(int j=1;j<=9;j++){
            for(int t=1;t<=9;t++){
                sum=i*100+j*10+t;
                if(sum*b[2]<=999){
                    a[0]=sum*b[0];
                    a[1]=sum*b[1];
                    a[2]=sum*b[2];
                    ans=judge(a);
                    if(ans==1){
                        printf("%d %d %d\n",a[0],a[1],a[2]);
                        k=0;
                    }
                }
            }
        }
    }
    if(k==1) printf("No!!!\n");
    return 0;
}

3.思路总结

??多读题，化繁为简，注意题目应该等价转换

P1464 Function

1.题目描述P1464

2.实现方法

??在做这道题的时候我联想到了c语言递归作业中族谱这道题，这道题如果直接用递归的方法实现会超时，所以就用了并查集干路压缩的方法来优化，让初始的人直接指向他们的祖先，减少递归的次数，达到优化的目的。这道题可以借鉴这种思路来达到优化的目的（将走过的路径保存下来），接下来的难点就在于如何实现了。

#include<stdio.h>
long long keep[25][25][25]={0};
long long w(long long int a,long long int b,long long c){
    if(a<=0||b<=0||c<=0) return 1;
    else if(keep[a][b][c]!=0) return keep[a][b][c];
    else if(a>20||b>20||c>20) keep[a][b][c]=w(20,20,20);
    else if(a<b&&b<c) keep[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
    else keep[a][b][c]=w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1);
    return keep[a][b][c];
}
int main(){
    int a,b,c;
    while(1){
        scanf("%d %d %d",&a,&b,&c);
        if(a==-1&&b==-1&&c==-1){
            break;
        }
        else{
            printf("w(%d, %d, %d) = ",a,b,c);
            if(a>20) a=21;
            if(b>20) b=21;
            if(c>20) c=21;
            printf("%d\n",w(a,b,c));
        }
    }
    return 0;
}

??将搜索的结果用数组存起来，避免反复搜索同一个值，这叫做记忆化搜索
PS.百度百科
记忆化搜索
一般说来，动态规划总要遍历所有的状态，而搜索可以排除一些无效状态。更重要的是搜索还可以剪枝，可能剪去大量不必要的状态，因此在空间开销上往往比动态规划要低很多。记忆化算法在求解的时候还是按着自顶向下的顺序，但是每求解一个状态，就将它的解保存下来，以后再次遇到这个状态的时候，就不必重新求解了。这种方法综合了搜索和动态规划两方面的优点，因而还是很有实用价值的。

3.思路总结

??在进行计算或其他过程时（递归或者数组循环运用），有部分运算被不断重复，可以考虑是否能用记忆化搜索来优化算法

2020.2.6限时训练总结（洛谷）

原文：https://www.cnblogs.com/beyondzones/p/12271479.html