摘要
Title: 1050. 鸣人的影分身
Tag: 完全背包、整数划分问题、dp
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

1050. 鸣人的影分身

• 题意

  在火影忍者的世界里，令敌人捉摸不透是非常关键的。
  我们的主角漩涡鸣人所拥有的一个招数——多重影分身之术——就是一个很好的例子。
  影分身是由鸣人身体的查克拉能量制造的，使用的查克拉越多，制造出的影分身越强。
  针对不同的作战情况，鸣人可以选择制造出各种强度的影分身，有的用来佯攻，有的用来发起致命一击。
  那么问题来了，假设鸣人的查克拉能量为 M，他影分身的个数最多为 N，那么制造影分身时有多少种不同的分配方法？
  注意：
  影分身可以分配0点能量。
  分配方案不考虑顺序，例如：M=7,N=3，那么 (2,2,3) 和 (2,3,2) 被视为同一种方案。

• 思路

  • 整数划分问题
    不能用隔板法，因为这里不考虑顺序
    
  • 完全背包
    目前不知道怎么证明正确性，但是是AC的

• 代码

  整数划分问题

  '''
  Author: NEFU AB-IN
  Date: 2022-04-02 16:07:09
  FilePath: \ACM\Acwing\1050.1.py
  LastEditTime: 2022-04-02 16:17:04
  '''
  for _ in range(int(input())):
      m, n = map(int, input().split())
      f = [[0] * 15 for _ in range(15)]
      f[0][0] = 1
      for i in range(0, m + 1): #因为总和可以都是0，所以i从0开始
          for j in range(1, n + 1):
              f[i][j] = f[i][j - 1] + f[i - j][j]
      print(f[m][n])

  ---

  完全背包

  for _ in range(int(input())):
      m, n = map(int, input().split())
      f = [0] * 15
      f[0] = 1
      for i in range(1, n + 1):
          for j in range(i, m + 1):
              f[j] += f[j - i]
      print(f[m])