话说大诗人李白, 一生好饮。幸好他从不开车。
一天, 他提着酒壶, 从家里出来, 酒壶中有酒 2 斗。他边走边唱:
无事街上走,提壶去打酒。 逢店加一倍, 遇花喝一斗。
这一路上, 他一共遇到店 NNN 次, 遇到花 MMM 次。已知最后一次遇到的是花,他正好把酒喝光了。
请你计算李白这一路遇到店和花的顺序, 有多少种不同的可能?
注意: 壶里没酒 ( 0 斗) 时遇店是合法的, 加倍后还是没酒; 但是没酒时遇 花是不合法的。
5 10
14
如果我们用 0 代表遇到花,1 代表遇到店,14 种顺序如下:
010101101000000
010110010010000
011000110010000
100010110010000
011001000110000
100011000110000
100100010110000
010110100000100
011001001000100
100011001000100
100100011000100
011010000010100
100100100010100
101000001010100
1≤N,M≤1001≤N,M≤1001≤N,M≤100
李白打酒加强版
比较明显是一道状态机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] 作为答案。
#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;
}