斑的家

#include<iostream>
#include<stdio.h>
#include<string.h>
#define SIZE  301
/*
 * AUTHOR: benbendog
 * DATE  : 2011/2/3
 * PROBLEM: partition of number, given a number <=300
            and a range[a,b] or only b , or nothing
            how many ways can the number be splitted in
            between [a,b] partitons.
 * SOLUTION: dp
             dp[i][j] = dp[i][j-1]+dp[i-j][j]; i>=j
             dp[0][0] = 1;
             dp[0][k] = 1; k > 0
             dp[k][0] = 1; k > 0
   dp[i][j] means number i , coins <= j.
   to obtain dp[i][j], dp[i][j-1] means coins <=j-1
   now we have to know the number of possibility of
   number i, coins = j. For dp[i-j][j], i-j means we
   substract 1 from ([j]) j coins, so
   when the possibility of number i, coins = j is
   equal to dp[i-j][j]
   for example:
        dp[6][4] = dp[6][3] + dp[2][4]
    dp[2][4] => 1+1+0+0,2+0+0+0
    dp[6][4] => 2+2+1+1,3+1+1+1
 */
using namespace std;
long long dp[SIZE][SIZE];
void init();
int main()
{
    char ch[10000];
    int t;
    int a,b,c;
    init();
    while(cin.getline(ch,10000))
    {
        t = sscanf(ch,"%d%d%d",&a,&b,&c);
       if(b >300)b = 300;
       if(c > 300)c = 300;
        switch(t)
        {

            case 1: printf("%ld\n",dp[a][a]);
            break;
            case 2: printf("%ld\n",dp[a][b]);
            break;
            case 3:
                if(b!=0)printf("%ld\n",dp[a][c] - dp[a][b-1]);
                else     printf("%ld\n",dp[a][c]);
        }
    }
    return 0;
}
void init()
{
    int i,j;
    dp[0][0] = 1;

    for(i = 1 ;i < SIZE;i++)
    {
        dp[i][0] = 0;
        dp[0][i] = 1;
    }
    for(i = 1 ; i < SIZE;i++)
        for(j = 1 ; j< SIZE;j++)
        {
            dp[i][j] = dp[i][j-1];
            if(i>=j)
                dp[i][j]+=dp[i-j][j];
        }
}