首页 > 其他 > 详细

小C的填数游戏

时间:2014-03-21 22:56:20      阅读:626      评论:0      收藏:0      [点我收藏+]

题意:

给出一张n个点的无向图 i连向i-1和i-2 边权为wij 有两个点权ai和bi ai为0或1

在给m个操作

1.将ai异或1

2.将区间x到y的点都填上一个数ci 使得Σ(bi*(ai^ci))+Σ((ci^cj)*wij) 输出最小值

 

题解:

30分算法:

  动规 f[i][j]表示前i个点后两个点的ci状态为j的最小值

  维护一次n^2但每次修改就要整个dp重做 特别浪费 时间复杂度O(nm)

正解:

  用线段树维护f数组 线段树一段维护前两点和后两点状态为i时的最小值

  这样每次修改log(n) 时间复杂度O(mlog(n))

小C的填数游戏,布布扣,bubuko.com

小C的填数游戏

原文:http://www.cnblogs.com/g-word/p/3616741.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!