动态规划：鸣人的影分身

Love The Way You Lie 2023-09-26 18:16 4阅读 0赞

在火影忍者的世界里，令敌人捉摸不透是非常关键的。

我们的主角漩涡鸣人所拥有的一个招数——多重影分身之术——就是一个很好的例子。

影分身是由鸣人身体的查克拉能量制造的，使用的查克拉越多，制造出的影分身越强。

针对不同的作战情况，鸣人可以选择制造出各种强度的影分身，有的用来佯攻，有的用来发起致命一击。

那么问题来了，假设鸣人的查克拉能量为 M，他影分身的个数最多为 N，那么制造影分身时有多少种不同的分配方法？

**注意**：

1.  影分身可以分配0点能量。

1.  分配方案不考虑顺序，例如：M=7,N=3，那么 (2,2,3)和 (2,3,2)被视为同一种方案。

##### **输入格式** #####

第一行是测试数据的数目 t。

以下每行均包含二个整数 M 和 N，以空格分开。

##### **输出格式** #####

对输入的每组数据 M和 N，用一行输出分配的方法数。

##### **数据范围** #####

0≤t≤20,

1≤M,N≤10

##### **输入样例：** #####

1
    7 3

##### **输出样例：** #####

8

**思路**：i代表所选数的总和，j代表已选数的个数，dp\[i\]\[j\]代表总和是i，且分成j个数的和的方案

#include<iostream>
    using namespace std;
    #define N 11
    int dp[N][N];
    int main()
    {
        int t;
        dp[0][0] = 1;//初始状态是1，即不选任何数也是一种方案
        cin >> t;
        while (t--)
        {
            int m, n;
            cin >> m >> n;
            for (int i = 0; i <= m; i++)
            {
                for (int j = 1; j <= n; j++)
                {
                    dp[i][j] = dp[i][j - 1];
                    if (i >= j) dp[i][j] = dp[i][j - 1] + dp[i - j][j];
                }
            }
            cout << dp[m][n] << endl;
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，4人围观）

还没有评论，来说两句吧...

相关阅读

相关动态规划：鸣人的影分身

在火影忍者的世界里，令敌人捉摸不透是非常关键的。我们的主角漩涡鸣人所拥有的一个招数——多重影分身之术——就是一个很好的例子。影分身是由鸣人身体的查克拉能量制造的，使用的

Love The Way You Lie/ 2023年09月26日 18:16/ 0 赞/ 5 阅读

相关动态规划

一：概念：和分冶法相似，不同之处在于前者是把问题划分为互不相交的子问题，而动态规划会出现子问题重叠的情况。通常用来求解最优化问题。。基本步骤： ①：刻画一个最优

我就是我/ 2022年12月01日 11:51/ 0 赞/ 42 阅读

相关动态规划

-------------------- 动态规划的设计思想动态规划（DP）\[1\]通过分解成子问题解决了给定复杂的问题，并存储子问题的结果，以避免再次计算相同的结

柔情只为你懂/ 2022年09月25日 11:15/ 0 赞/ 266 阅读

相关动态规划

作者：Hawstein 出处： [http://hawstein.com/posts/dp-novice-to-advanced.html][http_hawstein.c

淡淡的烟草味﹌/ 2022年09月24日 12:17/ 0 赞/ 219 阅读

相关 bnuoj 29065 鸣人的查克拉

鸣人的查克拉 Time Limit: 1000ms Memory Limit: 65536KB 64-bit integer IO format: %lld Java

旧城等待，/ 2022年08月26日 08:03/ 0 赞/ 16 阅读

相关动态规划

1. 首先，动态规划不是一个特定的算法，它代表的是一种思想，一种手段 2. 动态规划方法往往用于求解“最优化问题”，能用动态规划求解的问题的前提是问题具有“最优子结构性质”

刺骨的言语ヽ痛彻心扉/ 2022年07月29日 11:46/ 0 赞/ 113 阅读

相关动态规划

基本思想：动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。区别：与

ゞ浴缸里的玫瑰/ 2022年05月25日 09:44/ 0 赞/ 459 阅读

相关动态规划

等我有时间了，一定要把《算法导论》啃完，这本书的印刷质量实在太好了，就是烧脑子，滑稽。适合应用动态规划求解的最优化问题应该具备两个要素：最优子结构：一个问题的最优解包含

短命女/ 2022年05月17日 09:45/ 0 赞/ 341 阅读

相关动态规划

算法题中动态规划是真的难，写一篇总结，彻底解决动态规划。参考：[https://blog.csdn.net/u013309870/article/details/7519359

左手的ㄟ右手/ 2021年11月19日 14:14/ 0 赞/ 520 阅读

相关 Openjudge-4115-佐助和鸣人

这一题是一道广搜的题目，首先我们通过读入字符串读入每一行，然后顺带找到鸣人的位置。然后我们初始化之后，就进行广搜，还是广搜的格式，但是要压入队列的条件我们可以稍微变一变，我

ゞ浴缸里的玫瑰/ 2021年10月25日 13:22/ 0 赞/ 260 阅读