CodeForces 818G 费用流 优化建图

CodeForces 818G

题意

给定一个长度为$n$的序列$a_i$,$4 \leq n \leq 3000,1 \leq a_i \leq 10^5$,从中选出$4$个不想交的子序列,满足每个子序列中相邻的两个项,要么是差的绝对值为$1$,要么他们模$7$的结果相同。问这四个序列的总长度最长为多少。


思路

  • 对于每个项来说,将其看成一个点,将其拆点为为$i$和$i+n$,从$i$向$i+n$引一条边,容量为$1$,费用为$-1$,表示该点项只能被选一次,且选了之后收益$+1$。这一对点的流量方向,一定为从$i$进,并且从$i+n$出。
  • 对于每个项来说,都有可能作为子序列的起点或者终点。所以,从源点引一条边到$i$点,容量为$1$,费用为$0$;再从$i+n$点引一条边到汇点,容量为$1$,费用为$0$。
  • 对于每一个可能相邻的项$a_i,a_j$且$i \lt j$来说,需要建一条边从$i+n$到$j$,容量为$1$,费用为$-1$。但是这样建边之后,会发现边很多,根本跑不过。其实会发现,对于每一类相邻来说,只需要往后找到四个是同类的并建边就好了。
  • 从源点压入$4$点流量,跑费用流即可,答案为最小费用的相反数。

代码

发表评论

电子邮件地址不会被公开。 必填项已用*标注