UVA10910 - Marks Distribution(dp)

UVA10910 - Marks Distribution(dp)
제목 링크
제목의 뜻: N, T, P를 주고 F(N, T, P)를 찾으면 N개의 수를 요구한다. 각 수는 적어도 P보다 크고 T와 같은 조합 방식은 몇 가지가 있는가.
문제풀이 방향:DP,f[n+1][sum+i]+=f[n][sum];i 는 p부터 T - sum까지입니다.
코드:

#include <cstdio>
#include <cstring>

typedef long long ll;
const int maxn = 75;

int N, T, P;
ll f[maxn][maxn];

void init () {
    memset (f, -1, sizeof(f));
}

ll dp(int k, int sum) {

    ll& ans = f[k][sum];
    if (ans != -1)
        return ans;

    if (k == N) {
        if (sum == T)
            return ans = 1;
        return ans = 0;
    }

    ans = 0;
    for (int i = P; i <= T - sum; i++) {

        if (i + sum <= T)
            ans += dp(k + 1, sum + i);
        else
            break;
    }

    return ans;
}

int main () {

    int K;
    scanf ("%d", &K);

    while (K--) {

        scanf ("%d%d%d", &N, &T, &P);
        init();
        printf ("%lld
", dp(0, 0));
    }
    return 0;
}