Skip to content

11370: 【原1370】赫萝的桃子

题目

题目描述

author: SSY 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1370

Description

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

Input Format

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

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

接下来n行每行两个数a, b(a>b)。

Output Format

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

Sample Input

2
7 3
6 2

Sample Output

4
3

HINTS AND LIMITS

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

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

提示:可以用递归或者动态规划解决,答案保证在int范围内。

WashSwang's solution

#include <iostream>
#include <cstring>
using namespace std;
int n,a,b,t[41][161][161],ans,sum;//第i天吃j个总共k个
int main() {
    cin>>n;
    for (int q=0;q<n;++q)
    {
        memset(t,0,sizeof(t));
        cin>>a>>b;
        t[0][0][0]=1;
        for (int i=1;i<=b;++i){
            for (int k=0;k<=a;++k){
                sum=0;
                for (int j=0;j<=a-k;++j){
                    sum+=t[i-1][j][k];
                    if (j!=0) t[i][j][k+j]=sum;
                }
            }
        }
        ans=0;
        for (int i=1;i<=a;++i)
            ans+=t[b][i][a];
        cout<<ans<<endl;
    }
    return 0;
}

yyong119's solution

#include <cstdio>
#include <algorithm>
#define MAX_A 165
#define MAX_B 45
using namespace std;
int f[MAX_A][MAX_B];

int main() {
    int case_num;
    scanf("%d", &case_num);
    f[0][0] = 1;
    for (int i = 0; i < MAX_A; ++i)
        f[i][1] = 1;
    for (int i = 1; i < MAX_A; ++i)
        for (int j = 1; j <= min(i, MAX_B - 1); ++j)
            f[i][j] = f[i - 1][j - 1] + f[i - j][j];
    int a, b;
    while(case_num--) {
        scanf("%d%d", &a, &b);
        printf("%d\n", f[a][b] >> 1);
    }
    return 0;
}