当前位置:编程学习 > C/C++ >>

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++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,