题目描述
算法
(动态规划) $O(n * m * k *c)$
一看到这道题我马上就想到了类似走迷宫dp问题,
都是有方向性(即把酒喝完)和 步骤性(到酒店还是到花)的问题,
只是多了一些限制条件(例如最后一次是花 等等)
于是我们可以大胆假设:
dp算法:闫氏dp分析法 (yxc yyds)
解释:如果最后一步是到店,那么j应该大于0,因为至少有最后一步到店,到花同理,
如果最后一步是到店,那么上一步手里有的酒应该是k / 2,也是因此我们的k应该整除于2
如果最后一步是到花,那么上一步手里有的酒应该是k + 1。
注意:这里的方案都是合法方案
时间复杂度
由于n, m 最大为100,则李白手里的酒不应该超过100斗,否则遇上的花喝不完酒
因此 时间复杂度大概为:100 * 100 * 100 * 2 (10的6次方,okk)
C++ 代码(四重循环)
注意:初始化的时候我把 f[0][0][2][1] 初始化为1,其他f[0][0][k][c]都为0,
表示一开始只有李白手里拿2斗酒这一种情况。
(如果初始化 f[0][0][2][0] = 1,其他 f[0][0][k][c] 为0也可)
#include<bits/stdc++.h>
using namespace std;
const int N = 110, M = 1000000007;
int n, m, f[N][N][N][2];
int main()
{
scanf("%d%d", &n, &m); // 按照题目的来, 原先写成m个店, n朵花实在太蠢, 看得自己都一愣一愣的
for(int i = 0; i <= m; i ++ )
{
for(int j = 0; j <= n; j ++ )
{
for(int k = 0; k <= m; k ++ ) // 手中的酒枚举到m即可, 因为不会超过花的个数
{
for(int c = 0; c < 2; c ++ )
{
if(i == 0 && j == 0 && k == 2 && c == 1)
f[i][j][k][c] = 1;
if(i == 0 && j == 0)
continue;
if(j > 0 && c == 1 && k % 2 == 0)
{
f[i][j][k][c] = (f[i][j - 1][k / 2][0] + f[i][j - 1][k / 2][1]) % M;
}
if(i > 0 && c == 0 && k >= 0)
{
f[i][j][k][c] = (f[i - 1][j][k + 1][0] + f[i - 1][j][k + 1][1]) % M;
}
}
}
}
}
printf("%d", f[m][n][0][0]);
return 0;
}
(分割线)
这里再附上听完y总的题解的解法,时间复杂度O(n * m * k)
C++ 代码(三重循环)
注意:初始化的时候把 f[0][0][2] 初始化为1,其他 f[0][0][k] 都为0,
表示一开始只有李白手里拿2斗酒这一种情况。
最后打印答案的时候不是打印 f[n][m][0] ,因为这么打印是无法区分最后是到花还是到店,
我们可以往前推一步,如果最后到花,那么喝完的上一步应该是f[m - 1][n][1],
所以最后答案是f[m - 1][n][1]
#include<bits/stdc++.h>
using namespace std;
const int N = 110, M = 1000000007;
int n, m, f[N][N][N];
int main()
{
scanf("%d%d", &n, &m);
for(int i = 0; i <= m; i ++ )
{
for(int j = 0; j <= n; j ++ )
{
for(int k = 0; k <= m; k ++ ) // 手中的酒枚举到m即可, 因为不会超过花的个数
{
if(i == 0 && j == 0 && k == 2)
f[i][j][k] = 1;
if(i == 0 && j == 0)
continue;
if(i > 0)
f[i][j][k] = (f[i][j][k] + f[i - 1][j][k + 1]) % M;
if(j > 0 && k % 2 == 0)
f[i][j][k] = (f[i][j][k] + f[i][j - 1][k / 2]) % M;
}
}
}
printf("%d", f[m - 1][n][1]);
return 0;
}
清晰易懂,tql
老哥,三重循环那里为什么f[i][j][k]要加上自己本身的值啊
有两个if语句,前一个是 最后一步是花的语句,后一个是 最后一步是酒的语句,如果不加上本身的值,在两个条件都满足的时候就只会记录后一个 if 的值,所以一般记录方案数都是 +=
哦哦我懂了,多谢多谢
我也想过这个问题,听了楼下Rickkk老哥的解释,我把第一个+=改成了=,也能过,意思也是一样的
高手
赞!!!
谢谢支持!第一次写这么详细的题解
一起加油啊!!!
嗯,冲冲冲
为什么壶里的酒设置成不超过N啊/(ㄒoㄒ)/~~
不是不超过N, 准确来说是不超过M, 因为最后酒是喝光的, 所以酒的数量不可能比花的数量多, 而N和M是题目给的:
M, N<=100
, 至于为什么k枚举到99, 其实这里k也可以写成枚举到n, 因为我题解写的n是题目的m, 而m是题目的n, 现在才发现, 这题解太蠢了😂已更改
tqltql
f[0][0][2]初始化不是太明白 if(i > 0)
f[i][j][k] = (f[i][j][k] + f[i - 1][j][k + 1]) % M;
这里也不是太懂,大佬能解答一下吗
题目说李白一开始手里有2斗酒, 所以f[0][0][2]这种方案合法且只有一种。
第一个if是指此时遇到的是花, 那是喝了一斗酒, 那上一步应该比现在多一斗, 便可以得上一步是f[i - 1][j][k + 1]。
第二个if是指此时遇到的是店, 那是增加了一倍酒, 那上一步应该比现在少一半酒, 便可以得上一步是f[i][j - 1][k / 2]。
两种方案数加起来, 就是当前这一步的方案数
如果f[0][0][2]是合法的话,那么手里有两斗酒,如何经过0个店和0朵花,酒就变成0呢,这里不太理解为什么初始化为1
不是很理解你的意思啊, 哪个数据表示手里有2斗酒, 并且经过0个店和0朵花, 酒变成了0呢?这里的 f[ ][ ][ ] 数组表示的是方案数,题目说李白一开始有两斗酒,所以是1种方案,因此 f[0][0][2]为1,后续其他情况的方案数都是由最开始这个 “只有两斗酒” 推算来的
和我想的一样,我问的别人,他说这时相当于一动不动,一动不动就算是一种情况了
大佬我想问一下n和m为什么从0开始啊求教
是说循环的
i
和j
吧, 就按理来说我们应该初始化一个酒店和一个花都没有经过的情况,然后再循环去递推出其他. 这里呢, 因为会出现经过一个酒店而没有经过花的情况, 或者经过一个花没有经过酒店的情况, 即
f[0][1][k]
和f[1][0][k]
, 都要枚举到0, 所以就干脆都从0开始了, 然后初始化再特判一下即可别纠结了,像这样只初始第一步遇到店和第一步遇到花就好了,如果是copy楼主的代码记得把他的初始化语句删了
感谢
k为什么小于等于110就够了啊,不应该是很大吗
这里动态规划枚举的是各个方案,题目规定了李白遇店和遇花都不超过100次,因此枚举到100即可,110是因为y总代码多加了10,不过没关系,不符合条件的数据,最终答案并不会被使用到,可以简单理解为不符合条件的相当于多出来的路,但是李白并不会走,还是会走符合条件的路。
楼主可能对你的意思不清楚,但是我和你有同样疑问,所以我一开始觉得这种设法可能需要设置第三维为$2^{100}$,会导致数组太大,但是刚刚想了一下,遇到的花店最多就是100个,那么当你的k大于了100以后,就没有必要看了,因为这种方案肯定是不合法的,因为到了终点的酒的数量一定大于0。
tql,当时活生生想不出来😭
动态规划的题多做就会有感觉啦, 特别是y总的方法还比传统的简单易懂, 加油 !
k为什么会++呢,不是只有*2和-1两种情况吗
这里的四重循环是枚举每一步 ( 比如到了3个店2个花有1斗酒 ),
然后根据公式由前一步 ( 可能是好几种情况, 前一步可能最后到店也可能到花 ) 的可能情况的总数, 推出当前枚举的这一步的可能情况的总数 ( 就是当前这一步是确定的, 但是前面它怎么来的, 可是有好几种情况), 当然也可能当前这一步不合法, 那就一般等于0
可能我无法说清楚, 可以看y总b站视频讲解, BV18i4y1D7cJ
三维dp里面最后的答案应该是f[n-1][m][1]吧,楼主写错了
确实是写错了,多谢提醒