BZOJ 1283 序列 题解

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

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

不过DP倒是可以做k=1的情况。我们把k data-recalc-dims=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”(以上文字来源于论文)

STk次SPFA求最大费用最大流,就是答案啦!

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

 

发表评论

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

*