简单的DP

Distribute Message

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1345 Accepted Submission(s): 625

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 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

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

Author 威士忌

#include 
   
    
#include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 #include 
                
                  #include 
                 
                   #include 
                   using namespace std; #define MAXN 35 int dp[MAXN]; int main(){ int n,m; int i,j; while(~scanf("%d%d",&n,&m)){ if(n==0 && m==0){ break; } memset(dp,0,sizeof(dp)); dp[1] = 1; for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ if((i+j)<=n){ dp[i+j] = dp[i+j]+dp[i]; } } } printf("%d\n",dp[n]); } return 0; }

DP HDU 1723

Distribute Message