题目链接:传送门
Description
给定一个长为n(n<=5000)序列A,求最长下降子序列及方案数 ps:当二种方案“看起来一样”时(就是说它们构成的序列一样的时候),这2种方案被认为是相同的。如:2,1,1,1,1中方案数为1
Solution
对于第一问,我们直接跑一遍的LIS即可 对于第二问,我们记
TeX parse error: Undefined control sequence \[
表示到第i位,长度为TeX parse error: Undefined control sequence \[
的LIS的个数, 那么有TeX parse error: Undefined control sequence \[
对于判重,如果TeX parse error: Undefined control sequence \[
&&TeX parse error: Undefined control sequence \[
就说明这两种情况完全一样,所以对i位以前的j位进行清零。这样就能将cnt求出来了Code
1 |
|