9、李白打酒加强版

题目 李白打酒加强版

思路分析

很明显是个dp问题

考虑怎么把状态表示清楚

状态表示： f[i][j][k][c] 遇见了i次店 j次花 手上有k斗酒 且此时是在c（店/花）的所有情况的集合 属性：count

状态转移：

若此时为花 c=0 即f[i][j][k][0] 因为遇花喝一斗 说明上一个状态应该是 第j-1次遇见花 然后手上应该有k+1斗酒 不确定的是上一步到底是花还是店 但是情况是两者的选择数之和 所以直接加就行了

f[i][j][k][0]=f[i][j-1][k+1][0]+f[i][j-1][k+1][1];

若此时为店 c=1 即f[i][j][k][1] 因为遇店翻一倍 说明 上一个状态应该是 第i-1次遇到店 然后手上有k/2斗酒 同理 两个情况加一下

f[i][j][k][1]=f[i-1][j][k/2][0]+f[i-1][j][k/2][1];

考虑一下这两种方式有什么限制（一定要合法）

首先考虑遇花（当前位置是花） 什么情况才能合法遇花 上一步k大于0的情况才能喝一斗 所以k+1>0 k>-1

然后考虑遇店（当前位置是店） 什么情况才能合法遇店 遇店翻一番 如果此时的k不能被一个合法的k/2乘得到 就不合法 换句话说 k/2要是整数 那么条件就是 k%2==0

接下来考虑初始化

初始可以看作是 经过了0个店 0个花 然后手上有2斗酒 此时为c(店或者花）这个无所谓 姑且当做是店吧 的情况有1种 所以f[0][0][2][1]=1; 其他情况都是0种 不用管 自动初始0

最后的答案应该是 经过n个店 m个花 然后手上有0斗酒 且当前在花（0)时的所有选法数

取出f[n][m][0][0]即可

代码实现

#include<bits/stdc++.h>

using namespace std;

const int N=110,mod=1000000007;

int f[N][N][N][2];

int main()

{

	int n,m;

	cin>>n>>m;

	f[0][0][2][1]=1;

	for(int i=0;i<=n;i++){//店

		for(int j=0;j<=m;j++){//花

			for(int k=0;k<100;k++){//酒

				for(int c=0;c<2;c++){//当前位置

					if(j>0 && c==0 && k>-1)

						f[i][j][k][c]=(f[i][j-1][k+1][0]+f[i][j-1][k+1][1])%mod;

					if(i>0 && c==1 && k%2==0)

						f[i][j][k][c]=(f[i-1][j][k/2][0]+f[i-1][j][k/2][1])%mod;

				}

			}

		}

	}

	cout<<f[n][m][0][0];

	return 0;

}

同类题型

视频讲解

⬅️ 8、扫雷 🏠 00-刷题理模型 ➡️ 第十三届 c++ B组 省赛