Description

赫萝最喜欢吃蜂蜜腌渍的桃子。然而她能够得到的桃子有限，因此赫萝必须精打细算。赫萝在b天内可以得到a个桃子，每天赫萝至少吃一个桃子，她想知道她在a天内有多少种吃桃子的方法。吃桃子的顺序并不重要，也就是说赫萝认为“第一天吃一个桃子第二天吃两个桃子”和“第一天吃两个桃子第二天吃一个桃子”算一种方法。

Input Format

每个测试点有多组测试数据。

第一行一个数n，表示测试的数量。

接下来n行每行两个数a, b（a>b）。

Output Format

输出n行，每行一个数，表示方法数量。

Sample Input

27 36 2

Sample Output

43

HINTS AND LIMITS

对于70%的数据，a≤60，b≤15 。

对于100%的数据，a≤160，b≤40。

 

DP的原理不太好想，思路是这样的。

举一个例子。

比如 7 3

1 1 5

1 2 4

1 3 3

2 2 3

 

而 6 2

1 5 原型是 1 1 5

2 4 原型是 1 2 4

3 3 原型是 1 3 3

这里可以发现

dp[i][j] 和 dp[i-1][j-1] 有一个关系

 

再看 4 3

1 1 2 原型是 2 2 3 

发现 dp[i][j] 和 dp[i-j][j]也有关系

 

3+1 = 4 正好是结果

所以猜测

dp[i][j] = dp[i-j][j]  + dp[i-1][j-1]

 

分析一下可以 这个4的来源 分为两类

第一类  所有的都大于等于2的时候 等价于 每天减去1 的情况

第二类是 存在一个一天只吃1个桃子的情况 不能直接全减1 因为会出现0的情况 所以单独处理

　　　　　　把这个天 去掉 dp[i-1][j-1]  //也许会担心那么其他的一天只有桃子的情况呢 这个不用怕 因为是从小到大的迭代过程 所以 已经内涵了

 

#include 
     
      using namespace std;int dp[300][50],n,k,i,j;int main(){    int T;    cin>>T;    for(int k=0; k < T; ++k){        int a,b;        cin>>a>>b;        dp[0][0] = 1;        for (int i = 1; i <= a; ++i)        {            dp[i][1] = 1;        }         for (int i = 1; i <= a ; ++i){
   //遍历桃子数            for (int j=1; j <= b; ++j){
   //遍历天数                if(i>=j)//必须桃子数大于等于天数 (因为每天至少一个桃子)                    //分两种情况                    //第一种情况 所有天都至少吃两个桃子 等价于 dp[i-j][j] j天每天吃一个之后的等效                    //第二种情况 至少一天只吃一个桃子 所以把其中随便一天去掉 就是dp[i-1][j-1]                    dp[i][j] = dp[i-j][j] + dp[i-1][j-1];            }        }        cout<
      
       <