HUST——1110雪碧（简单DFS）-白红宇

HUST——1110雪碧（简单DFS）

阅读量：5264 次

发布时间：2019-06-14

本文共 1119 字，大约阅读时间需要 3 分钟。

1110: 雪碧

时间限制: 1 Sec

内存限制: 128 MB

提交: 18

解决: 6

题目描述

杨神最近特别喜雪碧，他现在有两瓶，他大晚上的在街上走，他逢店加一倍（雪碧），逢摊吃大虾并喝一瓶（雪碧）。这一路走过去，遇到店n次，大排档m次，已知最后1次是小摊，大伙正好把雪碧喝完。请你计算杨神遇到店和小摊的次序，合理的次序一共有多少种？

输入

多组测试数据,每组输入2个整数n和m(均不大于10)

输出

对于每组测试数据输出一行,值为符合条件的次序数.

样例输入

1 3

样例输出

显然题意可以转换成给你初始值x=2，给你n次将当前值乘2的机会和m次将当前值减1的机会，最后两者刚好用完且此时x=0的方案数有多少种。比赛刚开始以为是DP（DP恐惧症），后来发现应该是DFS，而且数据范围很小，暴力没问题。然后想着用三个参数来表示当前状态：（当前瓶子数，当前乘2的可用次数，当前减1的可用次数）。

写完后样例可以过了，但是题目中说了最后一次是小摊，即在此之前不可以把瓶子变为0。

然后重新加了个边界条件过了

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 using namespace std;typedef long long LL;#define INF 0x3f3f3f3fint ans=0;void dfs(int ping,int nn,int mm){ if(nn<0||mm<0||ping<0||(ping<=0&&nn>=1))//最后这个条件不能少，若乘2的机会还有但瓶子为0也算非法 return ; if(ping==0&&nn==0&&mm==0) { ans++; return; } else { dfs(ping*2,nn-1,mm); dfs(ping-1,nn,mm-1); }}int main(void){ int n,m,i,j; while (~scanf("%d%d",&n,&m)) { ans=0; dfs(2,n,m); cout<
                  
                   <

转载于:https://www.cnblogs.com/Blackops/p/5766357.html

你可能感兴趣的文章

ViewPager的onPageChangeListener里面的一些方法参数：