uva 10721 - Bar Codes(dp)
题目大意:给出n,k和m,用k个1~m的数组成n,问有几种组成方法。解题思路:简单dp,cnt[i][j]表示用i个数组成j, cnt[i][j] = ∑(1 ≤ t ≤min(k, j)) cnt[i - 1][t].
#include <stdio.h> #include <string.h> #define ll long long const int N = 105; ll cnt[N][N]; int n, k, m; void init() { memset(cnt, 0, sizeof(cnt)); cnt[0][0] = 1; } void solve() { init(); for (int i = 1; i <= k; i++) { for (int j = 1; j <= n; j++) { for (int t = 1; t <= m && t <= j; t++) cnt[i][j] += cnt[i - 1][j - t]; } } printf("%lld\n", cnt[k][n]); } int main () { while (scanf("%d%d%d", &n, &k, &m) == 3) { solve(); } return 0; }
补充:软件开发 , C++ ,