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

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

by Noble_Wolf @ 2024-11-29 20:03:55

@JXR_Kalcium时间承受不了

by w9095 @ 2024-11-29 20:04:06

@JXR_Kalcium 确实无关，但是 l_i,r_i 范围太大了开不下那么大的 DP 数组

by JXR_Kalcium @ 2024-11-29 20:05:58

@w9095 可不可以用 f_{i,j} 表示考虑到第 i 位数，最后一位所填数字在第 j 个区间内的方案数

by JXR_Kalcium @ 2024-11-29 20:07:14

@w9095 这样应该就不需要离散化了，但我尚不确定其中“区间”的定义

by w9095 @ 2024-11-29 20:07:16

@JXR_Kalcium 如果 j 指离散化后形成的区间，可以。

by w9095 @ 2024-11-29 20:07:53

@JXR_Kalcium 其余情况似乎比较困难？

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

@w9095 感激不尽！

by Glacial_Shine @ 2024-11-29 21:23:14

@w9095

一个区间里的值真相等吗？

比如说第一位 l, r 为 1, 3，第二位 l, r 为 1, 3，那第二位的值也不相等啊

by Glacial_Shine @ 2024-11-29 21:54:03

刚才唐了，其实直接 dp 好了。

by Glacial_Shine @ 2024-11-29 21:54:18

@JXR_Kalcium