🔍 解题思路

题意：有n的长度，k个木板，每个木板的长度最多为m，问有多少种组合方式，对于给定的组合是字典序的第多少个。

思路：用dp[i][j]表示后i个木板组成长度为j的有多少种情况。确定给定的组合是第几个的话，就从前往后数，奇数的木板，假如给定的长度为3，那么就答案就加上当它为1和2的时候后面的情况数，偶数的是长度从大到小加上它后面的情况。

#include <iostream>
#include <stdio.h>
using namespace std;

int BC[34][34][34];

int MIN(int a, int b){
	return (a>b) ? b : a;
}

void init(){
	for(int i = 0; i < 34; i++)
		for(int j = 0; j < 34; j++)
			for(int k = 0; k < 34; k++)
				BC[i][j][k] = -1;
}

int bc(int n, int k, int m){
	if(BC[n][k][m] != -1) return BC[n][k][m];
	if(k>n || n>m*k){
		BC[n][k][m] = 0;
		return 0;
	}
	if(k == 1){
		BC[n][1][m] = 1;
		return 1;
	}
	int res = 0;
	for(int l = 1; l < MIN(n, m+1); l++){
		res += bc(n-l, k-1, m);
	}
	BC[n][k][m] = res;
	return res;
}

int main() {
	int n,k,m;
	scanf("%d%d%d", &n, &k, &m);
	init();
	printf("%d\n", bc(n, k, m));
	int c;
	scanf("%d", &c);
	for(int i = 0; i < c; i++){
		char s[44];
		scanf("%s", s);
		int gs[44];
		int cnt = 0;
		int acc = 0;
		char qs = '1';
		for(int j = 0; j <= n; j++){
			if(j < n && s[j] == qs){
				acc ++;
			}
			else{
				qs = s[j];
				gs[cnt] = acc;
				cnt ++;
				acc = 1;
			}
		}
		int order = 0;
		int remain = n;
		for(int j = 0; j < k-1; j++){
			if(j%2==0){
				//找1的个数少的
				for(int l = 1; l < MIN(gs[j], remain); l++){
					order += bc(remain-l, k-1-j, m);
				}
			}
			else{
				//找0的个数多的
				for(int l = gs[j] + 1; l < MIN(m+1, remain); l++){
					order += bc(remain-l, k-1-j, m);
				}
			}
			remain -= gs[j];
		}
		printf("%d\n", order);
	}
	return 0;
}