(Relax DP1.2)UVA 10910 Marks Distribution(求通过n门课获得t分的情况数,每门课至少能获得p分)

/*
 * UVA_10910.cpp
 *
 *  Created on: 2013年12月17日
 *      Author: Administrator
 */


#include 
  
   
#include 
   
     #include 
    
      using namespace std; const int maxn = 105; /** * dp[i][j]: 表示通过i门课,获得j分的情况数 */ int dp[maxn][maxn]; int main(){ int t; scanf("%d",&t); while(t--){ memset(dp,0,sizeof(dp)); int n,t,p; scanf("%d%d%d",&n,&t,&p); int i; for(i = p ; i <= t ; ++i){ dp[1][i] = 1;//*** } int j,k; for(i = 2 ; i <= n ; ++i){ for(j = p ; j <= t ; ++j){ for(k = p ; k <= j-p ; ++k){ dp[i][j] += dp[i-1][j-k]; } } } printf("%d\n",dp[n][t]); } return 0; }