本文主要是介绍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)这篇关于dp + 计数，1954D - Colored Balls的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
