Distribute Message

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 605    Accepted Submission(s): 259

Problem Description

The contest’s message distribution is a big thing in prepare. Assuming N students stand in a row, from the row-head start transmit message, each person can transmit message to behind M personals, and how many ways could row-tail get the message?

 

Input

Input may contain multiple test cases. Each case contains N and M in one line. (0<=M<N<=30)

When N=0 and M=0, terminates the input and this test case is not to be processed. 

 

Output

Output the ways of the Nth student get message.

 

Sample Input

4 1 4 2 0 0

 

Sample Output

1 3

Hint

4 1 : A->B->C->D 4 2 : A->B->C->D, A->C->D, A->B->D

 

　　这题是一个简单的DP题，每一个点都将其方式保留起来，使得后面的点能够从前面得到信息。

　　代码如下：

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 using namespace std;  5  6 int way[35], N, M;  7  8 /*int get( int x )  9 {
     10     if( x == 1 ) 11     {
     12         return 1; 13     } 14     int ans = 0; 15     for( int j = 1; j <= M; ++j ) 16     {
     17         if( x - j >= 1 ) 18         {
     19             ans += get( x - j ); 20         } 21     } 22     return ans; 23 } DFS超时*/ 24 25 int main() 26 {
     27     while( scanf( "%d %d", &N, &M ), N|M ) 28     {
     29         memset( way, 0, sizeof( way ) ); 30         way[1] = 1; 31         for( int i = 1; i< N; ++i ) 32         {
     33             for( int j = 1; j <= M; ++j ) 34             {
     35                 if( i + j > N )  break; 36                 way[i+j] += way[i]; 37             } 38         } 39         printf( "%d\n", way[N] ); 40     } 41     return 0; 42 }