• 码蹄集 - MT2142 - 万民堂大厨



    万民堂大厨

    时间限制:1秒
    空间限制:128M


    题目描述

    万民堂大厨要做一道菜,这道菜需要烹饪数个小时,达到一定的火力值。可以选择小火烹饪一次加n点火力值,中火烹饪加m点火力值,大火烹饪加k点火力值,烹饪次数不限制。这道菜总共要达到x点火力值,不多不少,才能显现出万民堂大厨的实力。但万民堂大厨觉得这还是太简单了。所以他想考考你,这道菜有多少种不同的烹饪方式?(火力烹饪的顺序不同也算不同的情况,毕竟璃月厨艺博大精深,先小火后大火和先大火后小火烹饪的菜品会有很大不同)由于数据很大,请输出答案mod 1e9+7之后的值


    输入描述

    四个整数x,n,m,k

    数据范围

    所有数据均在long long范围内
    0 < x < 1000, 0 < n < m < k < 30


    输出描述

    一个整数,表示不同的方案数

    若无法烹饪则输出“impossible”


    样例一

    输入

    5 1 2 3
    
    • 1

    输出

    13
    
    • 1

    题目分析

    其实这道题的题目描述让我比较疑惑的是,数据范围为什么要加上个“long long范围内”,我寻思1000连INT_MAX都不到诶。

    这道题说白了,就是给你三个不同的数,每个数可以使用任意次。问你有多少种方案使得三个数之和是x,三个数顺序不同视为不同的方案

    好了,既然我们知道了题意,那么就可以开始愉快地dp了。

    建立一个长度至少为 x + 1 x + 1 x+1dp数组,初始值除 d p [ 0 ] = 1 dp[0]=1 dp[0]=1外全为 0 0 0

    d p [ i ] dp[i] dp[i]表示三个数之和为 i i i的方案数。

    那么,我们就可以用 i i i 1 1 1 x x x循环一遍,和为 i i i的方案有 3 3 3种,就是分别由 i − a 0 i-a_0 ia0 i − a 1 i-a_1 ia1 i − a 2 i-a_2 ia2得到。

    因此 d p [ i ] = ∑ j = 0 2 d p [ i − a [ j ] ] dp[i] = \sum_{j=0}^{2} dp[i - a[j]] dp[i]=j=02dp[ia[j]],其中 i ≥ a [ j ] i \geq a[j] ia[j]

    AC代码

    /*
     * @Author: LetMeFly
     * @Date: 2022-08-03 18:50:58
     * @LastEditors: LetMeFly
     * @LastEditTime: 2022-08-03 18:57:14
     */
    #include 
    using namespace std;
    #define mem(a) memset(a, 0, sizeof(a))
    #define dbg(x) cout << #x << " = " << x << endl
    #define fi(i, l, r) for (int i = l; i < r; i++)
    #define cd(a) scanf("%d", &a)
    typedef long long ll;
    
    ll dp[1010] = {1, 0};
    const ll mod = 1e9 + 7;
    
    int main() {
        int x;
        int val[3];
        cin >> x;
        for (int i = 0; i < 3; i++) {
            cin >> val[i];
        }
        for (int i = 1; i <= x; i++) {
            for (int j = 0; j < 3; j++) {
                if (i - val[j] >= 0) {
                    dp[i] += dp[i - val[j]];
                    dp[i] %= mod;
                }
            }
        }
        if (dp[x]) {
            cout << dp[x] << endl;
        }
        else {
            puts("impossible");
        }
        return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40

    虽然代码可以复制,但最好还是自己理解后再敲哦

    原创不易,转载请附上原文链接哦~
    Tisfy:https://letmefly.blog.csdn.net/article/details/126152888

  • 相关阅读:
    Python从基础到项目实战——基础篇
    Vue 绑定class样式
    GPE(Grafana+Prometheus+Exporter)项目实战之Golang篇(上)
    启动两个线程,用另一个线程以通知的终止另一个线程
    万字长文硬核AQS源码分析
    windows 11 install windows subsystem for android
    代码随想录day41|343. 整数拆分96. 不同的二叉搜索树
    vue-element-admin 集成框架解读----快速入门
    Jetson Xavier NX 平台JetPack 5.0.2 版本imx477-stereo camera调试
    盘一盘这个没资格出现在面试环节的场景题。
  • 原文地址:https://blog.csdn.net/Tisfy/article/details/126152888