有服务器怎么做网站教程,腾讯云10g数字盘做网站够么,重庆五号线金建站,网络营销最成功的企业一、题目
1、题目描述 2、输入输出
2.1输入 2.2输出 3、原题链接
Problem - 1954D - Codeforces 二、解题报告
1、思路分析
本题前置题目#xff1a;
1953. 你可以工作的最大周数
通过前置题目可以知道如何计算两两不同数对序列的最大长度
我们记最大数量为ma#xf…一、题目
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)状态有多少种每种(nma)有多少个
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)
