大佬求助蓝 DP 站外题，玄 5 关 QWQ

学术版

JXR_Kalcium @ 2024-11-29 19:45:06

题目。

by Noble_Wolf @ 2024-11-29 19:49:46

哥们打不开@JXR_Kalcium

by JXR_Kalcium @ 2024-11-29 19:51:13

@Noble_Wolf 可以的，https://www.luogu.com.cn/paste/nidituvo

by XiaoHongChong @ 2024-11-29 19:51:54

@JXR_Kalcium 有样例吗？

by JXR_Kalcium @ 2024-11-29 19:54:14

@XiaoHongChong 有的。

样例 #1

输入 #1

3
1 2
1 2
1 2

输出 #1

4

样例 #1 解释

合法序列有 (2,2,2),(2,2,1),(2,1,1),(1,1,1)。

样例 #2

输入 #2

10
24 73
57 82
10 99
27 777
11 289
22 73
57 81
10 900
27 1000
11 1145

输出 #2

839522421

by lowbit @ 2024-11-29 19:54:18

@JXR_Kalcium https://vjudge.net/problem/TopCoder-13278#author=0

by w9095 @ 2024-11-29 19:58:52

口胡做法：先把所有 l_i,r_i 离散化，记 y_x 为 x 对应的原值(y_{0}=0)，然后记 f_{i,j} 表示考虑完了第 i 个位置，填的数字为 y_{j-1}\sim y_{j} 的方案数，因为这些位置的数值一定是相等的。然后转移就平凡了。

我是蒟蒻，假了轻喷。

by JXR_Kalcium @ 2024-11-29 20:00:04

@w9095 我就是转移的地方有些不清楚

by w9095 @ 2024-11-29 20:00:54

@JXR_Kalcium 直接枚举小于这个数的位置累加过来

by w9095 @ 2024-11-29 20:01:24

@w9095 小于->大于等于

by JXR_Kalcium @ 2024-11-29 20:02:51

@w9095 求问为何需要离散化，转移应该与此无关吧

| 下一页