BZOJ 1283 序列 题解

题意:给出一个长度为 的正整数序列\(C_i\),求一个子序列,使得原序列中任意长度为\(m\)的子串中被选出的元素不超过\(k(k,m\le 100)\) 个,并且选出的元素之和最大。

考虑DP。。发现没法合理定义状态,放弃。。

不过DP倒是可以做\(k=1\)的情况。我们把\(k>1\)的情况分割成\(k\)个子问题,每个子问题为:求一个子序列,使得原序列中任意长度为\(m\)的子串中被选出的元素不超过\(1\)个,并且选出的元素之和最大。

那么\(k\)个不相交的子问题的解就是原问题的解(具体证明不太会,想了想发现好像是对的。。)

然后“构造带权网络G=(V,A,C) 序列中的每个元素i用顶点i与i’表示,i→i’连边,容量为1,费用为该元素的数值value[i],图中包含源S与汇T。 所有点i向点(i+1)连边,容量为+∞ ,费用为0。源S向所有点i各连一条边,容量为+∞,费用为0。所有点i’向汇T各连一条边,容量为+∞,费用为0。所有点i’向点(i+M)连边,容量为+∞ ,费用为0”(以上文字来源于论文)

从\(S\)到\(T\)跑\(k\)次SPFA求最大费用最大流,就是答案啦!

这样建图就是选了一个点之后强制从\(m\)个点之后的点开始寻找。。保证每长度为\(m\)的子串中最多只有一个元素。

 

发表评论

电子邮件地址不会被公开。

*