poj 1664 放苹果-白红宇

poj 1664 放苹果

阅读量：5809 次

发布时间：2019-06-18

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

这是一道简单的组合数学题，这里要用递推来做；

方法一：A[n][m] 表示n个盘子放m个苹果的方法,那么A[n][m] = A[n-1][m] + A[n][m-n];就会等于m个苹果放在n-1个盘子的方法（也就是一个盘子为0）加上我们个盘子放一个再把剩下的放到n个盘子；因为每个盘子中加一个数1不会影响A[n][m-n]中的方案的可行性，也不会影响A的定义。

View Code

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #include
                
                 #define LL long longusing namespace std;int Apple( int n,int m ){ if( m == 0 || n == 1 ) return 1; if( n > m ) return Apple( m , m ); else return Apple( n - 1, m ) + Apple( n , m - n ); }int main( ){ int T,n,m; while( scanf( "%d",&T )==1 ) { while( T-- ) { scanf( "%d %d",&m,&n ); printf( "%d\n",Apple( n , m ) ); } } //system( "pause" ); return 0;}

方法二：

这种方法比较好理解一点,就是后面的数一定不能小于前面的数：

也就是A[i-1]<=A[i];其实前面的方法是前面的数一定不能小于后面的数；

View Code

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #include
                
                 #define LL long longusing namespace std;int Apple( int t , int n , int m ){ if( t > m ) return 0; if( n == 1 ) return 1; int tt = m/n,sum=0; for( int i = t ; i <= tt ; i ++ ) sum += Apple( i , n - 1 , m - i ); return sum;}int main( ){ int T,n,m; while( scanf( "%d",&T )==1 ) { while( T-- ) { scanf( "%d %d",&m,&n ); printf( "%d\n",Apple( 0 , n, m ) ); } } //system( "pause" ); return 0;}

转载于:https://www.cnblogs.com/bo-tao/archive/2012/08/15/2640721.html

你可能感兴趣的文章