UVA 10721 Bar Codes

UVA_10721

    我们可以设f[i][j]表示第i个bar以第j个unit为结尾时情况的总数，那么f[i][j]=sum{f[i-1][k]}，j-k<=M。

#include<stdio.h>
#include<string.h>
#define MAXD 60
int N, K, M;
long long int f[MAXD][MAXD];
void solve()
{
    int i, j, k;
    memset(f, 0, sizeof(f));
    for(i = 1; i <= M && i <= N; i ++)
        f[1][i] = 1;
    for(i = 2; i <= K; i ++)
        for(j = i; j <= N; j ++)
            for(k = 1; k <= M && j - k > 0; k ++)
                f[i][j] += f[i - 1][j - k];
    printf("%lld\n", f[K][N]);
}
int main()
{
    while(scanf("%d%d%d", &N, &K, &M) == 3)
    {
        solve();
    }
    return 0;
}