P8786 题解

Xy_top · 2022-12-03 17:09:32 · 题解

看到都是顺次转移的动态规划，我来写一个贡献转移。

设 f[i][j][k] 为当前走到第 i 个位置，看了 j 次花，有 k 斗酒的方案数。

题目中说了初始两斗酒，那么 f[0][0][2]=1。

重点是怎么前推后，依次循环 i，j，k，

如果 f[i][j][k] 不是 0，那么我们在第 i+1 个位置看花或者经过酒店。

看花：走到第 i+1 个位置，看了 j+1 次花，酒的数量变为 k - 1。

酒馆：走到第 i+1 个位置，看了 j 次花，酒的数量变为 k \times 2。

状态转移方程：

if (f[i][j][k] != 0)//这里也可以简写成 if(f[i][j][k])
{
    f[i + 1][j + 1][k - 1] += f[i][j][k];
    f[i + 1][j][k * 2] += f[i][j][k];
}

注意！j 只需要循环到 m-1，不需要循环到 m，如果循环到了 m：

首先，再看花变成 m +1 已经对答案没有任何的贡献了。

其次，这样还会多算。如果不看花只能是没有酒，一直经过酒店，

但是题目要求最后一次只能经过花，所以不行。

还有一个问题：酒的斗数上线是什么？

显然不会超过 m，不然最后的酒就喝不完了，所以也循环到 m。

代码：

#include <iostream>
using namespace std;
int n, m;
int f[205][105][105];
int main() {
    cin >> n >> m;
    f[0][0][2] = 1;
    for (int i = 0; i < n + m; i ++)
        for (int j = 0; j < m; j ++)
            for (int k = 0; k <= m; k ++)
                if (f[i][j][k]) {
                    if (k > 0) f[i + 1][j + 1][k - 1] = (f[i + 1][j + 1][k - 1] + f[i][j][k]) % 1000000007;
                    if (k <= 50) f[i + 1][j][k * 2] = (f[i + 1][j][k * 2] + f[i][j][k]) % 1000000007;
                }
    cout << f[n + m][m][0];
    return 0;
}