一、題目

1、題目描述

2、輸入輸出

2.1輸入

2.2輸出

3、原題鏈接

Problem - 1954D - Codeforces

---

二、解題報(bào)告

1、思路分析

本題前置題目：

1953. 你可以工作的最大周數(shù)

通過(guò)前置題目可以知道如何計(jì)算兩兩不同數(shù)對(duì)序列的最大長(zhǎng)度

我們記最大數(shù)量為ma，總數(shù)目為N

如果ma > N / 2, 那么劃分的組數(shù)取決于ma，即ma組

如果ma <= N / 2, 那么劃分組數(shù)為floor(N / 2)

換句話說(shuō)，任意(N, ma)我們可以計(jì)算出其組數(shù)

那么(N, ma)狀態(tài)有多少種？每種(n，ma)有多少個(gè)？

n個(gè)顏色最多對(duì)應(yīng)n個(gè)ma，也就是說(shuō)我們最多有N * n種狀態(tài)

而N 和 n的上界都是5000

我們?nèi)绻x狀態(tài)f[總數(shù)][最大值]，那么每次狀態(tài)轉(zhuǎn)移需要遍歷比當(dāng)前最大值小的狀態(tài)，這樣的時(shí)間復(fù)雜度為O(n^3)

但是我們發(fā)現(xiàn)我們將原數(shù)組排序，那么我們順序遍歷的時(shí)候，最大值就是當(dāng)前值

我們考慮設(shè)計(jì)狀態(tài)f[i][x]為遍歷到第i個(gè)物品時(shí)，容量為x的方案數(shù)

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

而我們得知方案數(shù)后自然可以根據(jù)容量和當(dāng)前最大值nums[i]來(lái)計(jì)算其貢獻(xiàn)

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

我們發(fā)現(xiàn)這似乎退化成了01背包問(wèn)題，而且可以滾動(dòng)數(shù)組優(yōu)化

然后問(wèn)題就迎刃而解了

2、復(fù)雜度

時(shí)間復(fù)雜度： O(n^2)空間復(fù)雜度：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)