ZR9.8普转提_牛客博客

打过的CF原题,不管了

确认过眼神,是我不会写的DP,

发现这个题目要求的过程类似与一个所有括号都不一样的括号匹配的过程

但是限制条件非常多,有点无从下手的感觉

我们设\(f_{i,j}\)表示当\(i\)出栈前,\(i\)在栈底,\(i\)和他上面的所有物品重量不超过\(j\)时的最大价值

但是这样很难统计贡献,因为最终状态的栈是空的

我们考虑在栈的底部放一个永远不会被弹出的东西

他的参数是\(in:0,out:2\times n+1,w:0.s:w,v:0\)

对于所有物品按照\(out\)从小到大排序,\(out\)相同的按照\(in\)从大到小排序

这样就能满足括号序列的性质,使得尽可能多的出现这种情况,便于统计答案

我们枚举是那个物品在\(i\)的上面

这样我们就能直接转移

但只这样只是枚举了\([((((()))))]\)这样的情况,忽略了\([()()()()()]\)这样的情况

我们考虑用另外一个DP去考虑这种情况的贡献

我们设\(g_{i,j}\)表示前\(i\)时刻,重量为\(j\)的方案数

这样我们就可以在求得\(g_{a_i.out,u}\)之后,直接用这个东西去更新\(f_{i,u}\)

另外我们在DP的过程中,绝对不允许这种情况发生

我们可以看做分段DP,这种情况是不会放到一起被转移的

所以我们DP数组\(f\)和\(g\)都是定义在要么被\(i\)包含,要么完全不交的前提之下的

首先考虑暴力SB容斥

我们设\(f_i\)表示\(i\)这个集合里的物品不能选择的方案数

设\(U\)为全集

那么则有
\[ ans = \sum_{T\subseteq U} (-1)^{|T|}f_{\complement_{U}^T} \]
我们考虑如何计算\(f_i\)

设\(g_i\)表示包含的物品的对应二进制恰好为\(i\)的方案数,那么则有
\[ f_S = \sum_{T\subseteq S}g_T \]
这样我们就得到了一个\(3^m\)的做法

之后发现,求\(f_S\)的过程可以用FMT进行优化

然后时间复杂度为\(m \times 2 ^ m\)