dp + 计数，1954D - Colored Balls

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

Problem - 1954D - Codeforces

---

二、解题报告

1、思路分析

本题前置题目：

1953. 你可以工作的最大周数

通过前置题目可以知道如何计算两两不同数对序列的最大长度

我们记最大数量为ma，总数目为N

如果ma > N / 2, 那么划分的组数取决于ma，即ma组

如果ma <= N / 2, 那么划分组数为floor(N / 2)

换句话说，任意(N, ma)我们可以计算出其组数

那么(N, ma)状态有多少种？每种(n，ma)有多少个？

n个颜色最多对应n个ma，也就是说我们最多有N * n种状态

而N 和 n的上界都是5000

我们如果定义状态f[总数][最大值]，那么每次状态转移需要遍历比当前最大值小的状态，这样的时间复杂度为O(n^3)

但是我们发现我们将原数组排序，那么我们顺序遍历的时候，最大值就是当前值

我们考虑设计状态f[i][x]为遍历到第i个物品时，容量为x的方案数

那么f[i][x] = Σf[i -1][j - nums[i]]

而我们得知方案数后自然可以根据容量和当前最大值nums[i]来计算其贡献

然后我们用f[i][x]更新f[i + 1][x + nums[i]]即可

我们发现这似乎退化成了01背包问题，而且可以滚动数组优化

然后问题就迎刃而解了

2、复杂度

时间复杂度： O(n^2)空间复杂度：O(n)

3、代码详解

​

# import sys# sys.stdin = open('in.txt','r')
mod = 998244353n = int(input())
a = list(map(int, input().split()))a.sort()f = [0] * 5001
f[0] = 1res = s = 0
for x in a:for i in range(s, -1, -1):if f[i]:res = (res + f[i] * max((i + x + 1) // 2, x)) % modf[i + x] = (f[i] + f[i + x ]) % mods += xprint(res)