目录

• 1.李白打酒加强版
• • 1.题目描述
  • 2.输入格式
  • 3.输出格式
  • 4.样例说明
  • 5.数据规模
  • 6.原题链接
• 2.解题思路
• 3.Ac_code

1.李白打酒加强版

1.题目描述

话说大诗人李白, 一生好饮。幸好他从不开车。

一天, 他提着酒壶, 从家里出来, 酒壶中有酒 2 斗。他边走边唱:

无事街上走，提壶去打酒。 逢店加一倍, 遇花喝一斗。

这一路上, 他一共遇到店 NNN 次, 遇到花 MMM 次。已知最后一次遇到的是花，他正好把酒喝光了。

请你计算李白这一路遇到店和花的顺序, 有多少种不同的可能?

注意: 壶里没酒 ( 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≤1001≤N,M≤1001≤N,M≤100

6.原题链接

李白打酒加强版

2.解题思路

比较明显是一道状态机dp的题目，如何定义好状态可以帮助我们更好地初始化和转移以及求解答案，根据题目范围最大为100，比较明显暗示我们做法是一个O(n3)O(n^3)O(n3)的dp，dp状态也应该是三维的。定义状态f[i][j][k]f[i][j][k]f[i][j][k] 为已经遇到 iii 次店，jjj次花，还剩 kkk 斗酒的方案数。状态初始化明显是f[0][0][2]=1。

对于酒的上限数量，我们应该想好范围，因为花最多只有 mmm 朵，意味着我们最多只能喝 mmm 壶酒，对于 kkk 超过 mmm 的状态都是无效状态我们无需关心。所以剩余酒的上限也就是 kkk 应该也定为 mmm 。

考虑进行状态转移，对于状态f[i][j][k]f[i][j][k]f[i][j][k]，假设最后一次遇到的是店，那么此时需要保证 iii 大于0，并且 kkk 是偶数，因为遇到店剩余酒翻倍，kkk 一定不可能为奇数，那么可以得到转移方程
f[i][j][k]=(f[i][j][k]+f[i−1][j][k/2])%modf[i][j][k] = (f[i][j][k] + f[i - 1][j][k / 2]) \% modf[i][j][k]=(f[i][j][k]+f[i−1][j][k/2])%mod

假设最后一次遇到的是花，那么此时只需要保证 jjj 大于 0即可，我们可以获得转移方程f[i][j][k]=(f[i][j][k]+f[i][j−1][k+1])%modf[i][j][k] = (f[i][j][k] + f[i][j - 1][k + 1]) \% modf[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
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair 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;
}