BZOJ 1283 序列

发布于 2017-05-17  179 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1283

题意:给出一个长度为 n 的序列,对于序列中任意长度为 m 的子序列,不可以选超过 k 个数,求能选出的最大和...


最大费用最大流,自己 YY 了一个 k 个点一组汇到两个点的智障建模... 结果不对,于是看了题解... 建模什么的还是要学习一个啊...

正解是这样的:对于序列中两个相邻的元素,用一条流量 k,费用 0 的边相连,对于第 i 个元素,与第 i+m 个元素间连一条流量 1,费用 a[i] 的边... 这样做可以保证任意处的最大流都不超过 k,即不会选超过 k 个啦~然后让费用最大即可... 然而不会最大费用流,所以随便 YY 了一下,建图时费用取相反数,输出答案相反数即可...M 再次开小,RE 一发... 代码如下:

 


一个非常弱的准退役OIER