2019暑假集训第三天-（递推算法）

约定不等于承诺〃 2024-04-17 15:09 31阅读 0赞

### 1.走楼梯（stairs） ###

![在这里插入图片描述][20190827180000368.png]

#include <bits/stdc++.h>
    
    using namespace std;
    int climbStairs(int n) 
    { 
        if(n < 1)
            return 0;
        if(n == 1)
            return 1;
        if(n == 2)
            return 2;
    
        return climbStairs(n-1) + climbStairs(n-2);
    }
    int main()
    { 
     int n;
     cin>> n;
     cout<< climbStairs(n)<< endl;
    
    return 0;
    
    }

*  参考文章：https://blog.csdn.net/li1376417539/article/details/90673110
 *  https://blog.csdn.net/ajiangfan/article/details/52822411

### 2. 兔子繁殖（rabbit） ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70]

#include <bits/stdc++.h>
    
    using namespace std;
    int main()
    { 
     long long int a[105],b[105];     
     int n,i,m;
     scanf("%d",&n);
     a[1] = 0;                  
     b[1] = 1;             //第一月份的大小兔子数。
     a[2] = 1;                  
     b[2] = 0;                //第二月份的大小兔子数。
     for(i = 3;i <= n;i++)       
     { 
      b[i] = a[i - 1];          //某月的小兔子产数
      a[i] = a[i - 1] + b[i - 1];   //下个月产小兔子量（==这个月大兔子加上一个月的小兔子量） 
     }
     m = b[n] + a[n];                 //兔子总数
     printf("%d",m);           
     return 0;
    }

### 3. 平面分割（surface） ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 1]

#include<iostream>
    
    using namespace std;
    int main()
    { 
        int n,m;
        cin>>n>>m;
        int total=2*m;
        for (int i=m+1;i<=n;i++)
        total+=i;
        cout<<total;
    
    }

*  参考文章：https://blog.csdn.net/uiqrm/article/details/54666655

### 4. 骨牌铺法（domino） ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 2]

//include<AC自动机>
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<string>
    long long b[10001];
    using namespace std;
    int main()
    { 
        int m;
        cin>>m;
        b[1]=1;
        b[2]=1;
        b[3]=4;
        for(int i=4;i<=m;i++)
        { 
            b[i]=b[i-1]+b[i-2]+b[i-3];
        }
        cout<<b[m];
        return 0;
    }

*  参考文章：https://www.cnblogs.com/sssy/p/6601808.html

### 5. 蜜蜂路线（bee） ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 3]

/* *Copyright (c)2014,烟台大学计算机与控制工程学院 *All rights reserved. *文件名称：HDU.cpp *作 者：单昕昕 *完成日期：2015年1月19日 *版 本 号：v1.0 * *问题描述：有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。请编程计算蜜蜂从蜂房a爬到蜂房b的可能路线数。 其中，蜂房的结构如上所示。 *程序输入：输入数据的第一行是一个整数N,表示测试实例的个数，然后是N 行数据，每行包含两个整数a和b(0<a<b<50)。 *程序输出：对于每个测试实例，请输出蜜蜂从蜂房a爬到蜂房b的可能路线数，每个实例的输出占一行。 Sample Input 2 1 2 3 6 Sample Output 1 3 */
    #include<iostream>
    using namespace std;
    int main()
    { 
        long long f1,f2,temp;
        int n,m,k;
        cin>>n;
        while(n--)
        { 
            cin>>m>>k;
            f1=1;f2=1;
            for(int i=1;i<k-m;i++)
            { 
                temp=f1+f2;
                f1=f2;
                f2=temp;
            }
            cout<<f2<<endl;
        }
        return 0;
    }

*  参考文章：https://blog.csdn.net/MIKASA3/article/details/42874499

### 6. 极值问题（acme） ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 4]

# include<stdio.h>
    long long f[10005];
    int main(){ 
    	int n;
    	scanf("%d",&n);
    	f[1]=1;
    	f[0]=1;
    	f[2]=2;
    	int i;
    	if(n<=1) { 
    		printf("2\n");
    	}
    	else 
    	for(i=3;;i++)              //两种可能的情况
    	{ 
    		f[i]=f[i-1]+f[i-2];
    		if(f[i]>n)        //注意 
    		{ 
    		printf("%lld\n",f[i-1]*f[i-1]+f[i-2]*f[i-2]);	
    		break;
    		}
    		else if(f[i]==n) //注意 
    		{ 
    			printf("%lld\n",f[i]*f[i]+f[i-1]*f[i-1]);
    			break;
    		}
    	}
    	
    	
    	return 0;
    }

*  参考文章：https://blog.csdn.net/wx2306/article/details/79821423
 *  https://blog.csdn.net/PR\_sc/article/details/77199017

### 7. 火车站（NOIP1998） ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 5]

#include<map>
    #include<set>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include<cctype>
    #include<cstring>
    #include<utility>
    #include<cstdlib>
    #include<iomanip>
    #include<iostream>
    #include<algorithm>
    #define Clear(x) memset(x,0,sizeof(x))
    #define fup(i,a,b) for(int i=a;i<b;i++)
    #define rfup(i,a,b) for(int i=a;i<=b;i++)
    #define fdn(i,a,b) for(int i=a;i>b;i--)
    #define rfdn(i,a,b) for(int i=a;i>=b;i--)
    typedef long long ll;
    using namespace std;
    const int maxn = 1e2+7;
    const int inf = 0x3f3f3f3f;
    const double pi=acos(-1.0);
    const double eps = 1e-8;
    int f1[maxn];
    int f2[maxn];
     
    int read()
    { 
        char ch=getchar();int ret=0,f=1;
        while(ch<'0'||ch>'9'){ if (ch=='-') f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){ ret=ret*10+ch-'0';ch=getchar();}
        return f*ret;
    }
     
    int main()
    { 
        int a=read(),n=read(),m=read(),x=read();
        Clear(f1),Clear(f2);
        f1[1]=0,f1[2]=1;
        f2[1]=1,f2[2]=1;
        if(x==1||x==2)
        { 
            printf("%d\n",a);
        }else if(x==3){ 
            printf("%d\n",2*a);
        }else{ 
            rfup(i,3,n-3)
            { 
                f1[i]=f1[i-1]+f1[i-2];
                f2[i]=f2[i-1]+f2[i-2];
            }
            int sum1=2,sum2=0;
            rfup(i,1,n-4)
            { 
                sum1+=f1[i];
                sum2+=f2[i];
            }
            int man=(m-a*sum1)/sum2;
            sum1=2,sum2=0;
            rfup(i,1,x-3)
            { 
                sum1+=f1[i];
                sum2+=f2[i];
            }
            printf("%d\n",sum1*a+man*sum2);
        }
        return 0;
    }

*  参考文章：https://blog.csdn.net/cggwz/article/details/77200498
 *  https://blog.csdn.net/qq\_41311604/article/details/81544002
 *  https://blog.csdn.net/earnMoney/article/details/78079536

[20190827180000368.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/922063fc424b4c13a0ccb04082b8fcba.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/82f80c7d48d3423d815678ab25952856.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/e52bc5209bf64dfd8681d820a613abe3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/f68374c914444922b150e279c75f72ce.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/bce513a3292d4fe3a1cd60adcf3ab36f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/d3b83088077946b9b85a73c971b94f43.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dpdGh1Yl8zOTUzMzQxNA_size_16_color_FFFFFF_t_70 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/51cf06b4688d495694bacf52e93c70e8.png