NOIP集训-10.12总结

文件列表: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))