最直接的做法,算是回溯吧:
- 生成指定01数的序列
- 挨个检查是否满足题意并计数
能不能将生成和判断的过程统一呢?能不能记忆前面的序列呢
瞄一眼题解,往动态规划的方向上靠
#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
标签:13,加强版,int,蓝桥,110,省赛,dp,题意 From: https://www.cnblogs.com/yaocy/p/17188960.html