NOIP集训-10.12总结

YYY posted @ 2015年10月12日 14:40 in OI相关 with tags 模拟搜索优先队列 , 564 阅读

_THIS_IS_START_OF_ARTICLE_

文件列表：superoj920

模拟题...

编译优化 : superoj921

类似于最大流残留网络的思想

选择某个数之后，把它的值改为它左右两个数的值之和减去这个数的值

这样如果决定要“反悔”，即再选一次这个数，答案刚好变为其左右两数之和

然后每次用优先队列找出要选的数即可

这道题考试的时候我写了个60分的DP（然而只得了55分）：

首先枚举第一个点选不选，把环变成一个序列

然后设f(l,r,m)表示[l,r]这个区间,选m个的最大值

显然有:f(l,r,m) = max{f(l+1,r,m) , f(l+2,r,m-1) + a[l]}

第一种是不选最左边的点，第二种是要选

这个的时间复杂度是O(nm)的..

树形图计数：superoj922

枚举每个节点的父亲并验证就可以了,时间复杂度O(8 * (7^8))

_THIS_IS_END_OF_ARTICLE_

YYY