AcWing 1050. 鸣人的影分身【动态规划】【线性DP】【《信息学奥赛一本通》】

一、题目链接二、题目分析

（一）算法标签（二）解题思路 三、AC代码四、其它题解

AcWing 1050. 鸣人的影分身

DP 线性DP

解法一:

#include 
#include 
#include 

using namespace std;

const int N = 11;

// f[i][j] 表示总和为i, 用了j个数的方案数
int f[N][N];
int t, m, n;

int main()
{
    cin >> t;
    while (t -- )
    {
        scanf("%d%d", &m, &n);  // m能量, n个数
        f[0][0] = 1;
        for (int i = 0; i <= m; i ++ )
            for (int j = 1; j <= n; j ++ )
            {
                f[i][j] = f[i][j - 1];  // 最小值为0的情况：总和还是i，去掉一个0，还剩j-1个数
                if (i >= j) f[i][j] += f[i - j][j]; // 最小值非0的情况：每个数减1，总和为i-j，还是j个数
            }
        cout << f[m][n] << endl;
    }
    return 0;
}

AcWing 1050. 鸣人的影分身

AcWing 1050. 极简做法：查克拉分配分身=(苹果放置盘子)