第十三届蓝桥杯C++B组省赛 I 题——李白打酒加强版 （AC）
目录
- 1.李白打酒加强版
- 1.题目描述
- 2.输入格式
- 3.输出格式
- 4.样例说明
- 5.数据规模
- 6.原题链接
- 2.解题思路
- 3.Ac_code
1.李白打酒加强版
1.题目描述
话说大诗人李白, 一生好饮。幸好他从不开车。
一天, 他提着酒壶, 从家里出来, 酒壶中有酒 2 斗。他边走边唱:
无事街上走，提壶去打酒。 逢店加一倍, 遇花喝一斗。
这一路上, 他一共遇到店 N N N 次, 遇到花 M M M 次。已知最后一次遇到的是花，他正好把酒喝光了。
请你计算李白这一路遇到店和花的顺序, 有多少种不同的可能?
注意: 壶里没酒 ( 0 斗) 时遇店是合法的, 加倍后还是没酒; 但是没酒时遇 花是不合法的。
2.输入格式
5 10
3.输出格式
14
4.样例说明
如果我们用 0 代表遇到花，1 代表遇到店，14 种顺序如下：
010101101000000
010110010010000
011000110010000
100010110010000
011001000110000
100011000110000
100100010110000
010110100000100
011001001000100
100011001000100
100100011000100
011010000010100
100100100010100
101000001010100
5.数据规模
1 ≤ N , M ≤ 100 1≤N,M≤100 1≤N,M≤100
6.原题链接
李白打酒加强版
2.解题思路
比较明显是一道状态机dp的题目，如何定义好状态可以帮助我们更好地初始化和转移以及求解答案，根据题目范围最大为100，比较明显暗示我们做法是一个
O
(
n
3
)
O(n^3)
O(n3)的dp，dp状态也应该是三维的。定义状态
f
[
i
]
[
j
]
[
k
]
f[i][j][k]
f[i][j][k] 为已经遇到
i
i
i 次店，
j
j
j次花，还剩
k
k
k 斗酒的方案数。状态初始化明显是f[0][0][2]=1。
对于酒的上限数量，我们应该想好范围，因为花最多只有 m m m 朵，意味着我们最多只能喝 m m m 壶酒，对于 k k k 超过 m m m 的状态都是无效状态我们无需关心。所以剩余酒的上限也就是 k k k 应该也定为 m m m 。
考虑进行状态转移，对于状态
f
[
i
]
[
j
]
[
k
]
f[i][j][k]
f[i][j][k]，假设最后一次遇到的是店，那么此时需要保证
i
i
i 大于0，并且
k
k
k 是偶数，因为遇到店剩余酒翻倍，
k
k
k 一定不可能为奇数，那么可以得到转移方程
f
[
i
]
[
j
]
[
k
]
=
(
f
[
i
]
[
j
]
[
k
]
+
f
[
i
−
1
]
[
j
]
[
k
/
2
]
)
%
m
o
d
f[i][j][k] = (f[i][j][k] + f[i - 1][j][k / 2]) \% mod
f[i][j][k]=(f[i][j][k]+f[i−1][j][k/2])%mod
假设最后一次遇到的是花，那么此时只需要保证
j
j
j 大于 0即可，我们可以获得转移方程
f
[
i
]
[
j
]
[
k
]
=
(
f
[
i
]
[
j
]
[
k
]
+
f
[
i
]
[
j
−
1
]
[
k
+
1
]
)
%
m
o
d
f[i][j][k] = (f[i][j][k] + f[i][j - 1][k + 1]) \% mod
f[i][j][k]=(f[i][j][k]+f[i][j−1][k+1])%mod
我们还得考虑答案输出什么，题目要求最后一次遇到的必须是花，那么我们直接输出
f
[
n
]
[
m
]
[
0
]
f[n][m][0]
f[n][m][0] 肯定是错误的答案。 因为这并不能保证最后一次遇到的是花，因为最后是0壶酒，那么在遇到最后一朵花时应该还剩1壶酒，所以我们可以输出
f
[
n
]
[
m
−
1
]
[
1
]
f[n][m-1][1]
f[n][m−1][1] 作为答案。
3.Ac_code
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
#define pb(s) push_back(s);
#define SZ(s) ((int)s.size());
#define ms(s,x) memset(s, x, sizeof(s))
#define all(s) s.begin(),s.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 110;
int n, m;
//已经遇到i次店,j次花,还剩k斗酒的方案数
LL f[N][N][N];
void solve()
{
cin >> n >> m;
f[0][0][2] = 1;
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
for (int k = 0; k <= m; ++k) {
//最后一次遇到店
if (i && k % 2 == 0) f[i][j][k] = (f[i][j][k] + f[i - 1][j][k / 2]) % mod;
//最后一次遇到花
if (j) f[i][j][k] = (f[i][j][k] + f[i][j - 1][k + 1]) % mod;
}
}
}
cout << f[n][m - 1][1] << '\n';
}
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
while (t--)
{
solve();
}
return 0;
}