洛谷$P3308\ [SDOI2014]LIS$ 网络流

正解:网络流

解题报告:

传送门$QwQ$

恩先不考虑关于那个附加属性的限制,考虑这题怎么做?

首先这题从名字开始就让人忍不住联想起网络流24题里的那个最长不下降子序列?于是同样考虑预处理一个$f$呗

然后再一看,长得就很最小割嘛,于是拆点,能构成最长不下降子序列的之间就连权值为$inf$的边,$f_{i}=1$的点和$S$.$f_{i}=mxf$的点和$T$连权值为$inf$的边,拆开的点之间连权值为$b_{i}$的边.跑个最小割就好$QwQ$

现在考虑怎么搞那个附加属性$QwQ$?

不会,咕了,明天写$yep$

上一篇:@loj - 2196@「SDOI2014」Lis


下一篇:BZOJ 3529: [Sdoi2014]数表