蓝桥-13届-C++-B组-省赛-I题-李白打酒加强版

最直接的做法，算是回溯吧：

1. 生成指定01数的序列
2. 挨个检查是否满足题意并计数

能不能将生成和判断的过程统一呢？能不能记忆前面的序列呢

瞄一眼题解，往动态规划的方向上靠

#include<iostream>
using namespace std;
const int MOD = 1e9 + 7;
// 第i次相遇，遇到j次店，酒量为k的方案数
// k不可能超过遇花数，遇花数不超过100
int dp[210][110][110];

int main() {

	int n, m;
	cin >> n >> m;
	// 最后一次是花，而且正好喝完了，也就是说最后一次是-1=0
	// 问有多少种可能？按理来说是2^n+m种可能性最多，但是要保证符合题意
	// 构造所有可能然后一一检查？！这个怕是不太现实，2^200，至少也要做剪枝
	// 不对，如果制定了01的数量的话，应该是不会到这么大的
	// 或者是自己来组合生成所有可能的结果？
	dp[0][0][2] = 1;
	for (int i = 1; i <= n + m - 1; i++) {
		for (int j = 0; j <= n; j++) {
			for (int k = 0; k <= m; k++) {
				// 为什么遇店不为0且酒量为偶数？
				// 偶数表示上一次遇到的可以是店，这又要求了上一次店数>0
				// 同时也可以是花
				if (j != 0 && k % 2 == 0)
					dp[i][j][k] = (dp[i - 1][j][k + 1] + dp[i - 1][j - 1][k / 2]) % MOD;
				// 上一次只能是花
				else  dp[i][j][k] = dp[i - 1][j][k + 1];
			}
		}
	}
	cout << dp[n + m - 1][n][1] << endl;
	return 0;
}

我想不到，而且还是第一见三维数组的DP