BZOJ 2259 [Oibh] 新型计算机

发布于 2017-07-06  216 次阅读


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

题意:给定一个序列,读入方式为读一个数 x,读 x 个数,再读一个 y... 显然不一定能正好读完,修改一些数使得能正好读完,费用为和原数的差的绝对值,输出最小费用


如果能想到最短路模型就不困难了...

读入一个数 x 相当于向后跳了 x 个数,连一条权值为 0 边即可。修改操作相当于在相邻的前后连权值为 1 的边

需要注意的是,修改后应仍然为自然数,所以需要特殊判断一下哪些可以连

 


一个非常弱的准退役OIER