UVa 10721 - Bar Codes

传送门

UVa 10721 - Bar Codes

题意

给n根线条,求不每个bar不超过k根线的时候m个bar的方案。

思路

$dp[i][j]$表示i个bar用j个线

\[dp(i, j) = dp(i - 1, k)\]

代码

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#pragma comment(linker, "/STACK:102400000,102400000")
const int MAXN = 50;
 
LL dp[55][55];
 
int main()
{
    int n, k, m, i, j;
    while (~scanf("%d%d%d", &k, &m, &n))
    {
        memset(dp, 0, sizeof dp);
        for (i = 1; i <= k && i <= n; i++)
            dp[1][i] = 1;
        for (i = 2; i <= m; i++)
            for (j = i; j <= k; j++)
                for (int l = 1; l <= j && l <= n; l++)
                    dp[i][j] += dp[i - 1][j - l];
        printf("%lld\n", dp[m][k]);
    }
    return 0;
}

Powered by Jekyll and Theme by solid