求大佬捞捞60分
查看原帖
求大佬捞捞60分
1052426
REx2341楼主2025/1/16 23:09
#include <bits/stdc++.h>
using namespace std;
 long long f[210][199][199];
int n, m;
int main() {
    cin >> n >> m;
    // 初始状态,2斗酒
    f[0][0][2] = 1;
    // 开始递推过程,i 表示已经走的步数
    for (int i = 0; i < n + m; i++) {
        // j 表示已经遇到花的次数
        for (int j = 0; j < m; j++) {
            // k 表示某种与遇花次数相关的状态,这里可能是剩余遇花次数的倍数
            for (int k = 0; k <= m; k++) {
                // 当当前状态 f[i][j][k] 有走法时
                if (f[i][j][k] > 0) {
                    // 遇到花的情况
                    if ( k > 0) {
                        // 走了一步,遇到花的次数加 1,剩余的遇花次数减 1
                        f[i + 1][j + 1][k - 1] = (f[i + 1][j + 1][k - 1] + f[i][j][k]) % 1000000007;
                    }
                    // 遇到酒馆的情况
                    if (i + j < n + m) {
                        // 走了一步,遇到花的次数不变,剩余的遇花次数翻倍
                        f[i + 1][j][k * 2] = (f[i + 1][j][k * 2] + f[i][j][k]) % 1000000007;
                    }
                }
            }
        }
    }
    // 输出最终结果,即走了 n+m 步,遇到 m 次花,且最终状态为 0 的走法数
    cout << f[n + m][m][0] << endl;

    return 0;
}
2025/1/16 23:09
加载中...