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;
}