文章来源: http://thunderfyc.wordpress.com.cn
枚举
状态的简单枚举
可以简单表示的单参数状态，对每个状态计算得到结果判断是否相等
状态压缩表示
将状态压缩表示 如一组数 选择与不选用0和1表示 然后枚举
对已知答案集的枚举
知道答案的范围 然后对答案进行枚举判断是否符合条件
步长叠进枚举
知道答案 并且答案对情况的影响连续变化 通过大步寻找小范围 然后小步寻找答案的方法解 通常为几何问题
贪心
和DP类似 满足最优子结构 同时满足最优选择 即能导出最优子结构的选择唯一可判定
分治 二分
将问题分解为子问题 子问题共同对问题产生贡献
答案二分 单调决策序列二分
归并排序
将序列拆为一个元素长的若干序列 然后合并的时候将相邻的序列合并 最后合并为一个大的
快速排序
选定一个轴将小的放在左边 大的放在右边 然后分别继续处理两边
二分解方程
确定一个范围 满足f(l) f(r)异号 然后计算mid=(l+r)/2 找到f(l) f(r)中和f(mid)异号的 缩小范围 继续
LIS的二分优化
找到一个序列中的最长不下降序列
记录t[x]为长度为x的LIS的最后一个元素大小 要尽可能的小 可见t[]是有序的数组
每插入一个a[i] 如果a[i]比某个t[k]小 比t[k-1]大 那么a[i]替换这个t[k] 满足条件 如果比t[x]要大 t[x+1]为a[i] 整个序列的LIS拉长一位
文章来源: http://thunderfyc.wordpress.com.cn
=============================================================================
8×8棋盘上八皇后摆放 棋盘每格有分数 最后八皇后占据格子分数最大
求出所有摆放方案 枚举方案 计算
三个食物有不同的营养成分 选取每个食物的份数 最后让营养成分成要求的比例
枚举每个食物的份数 计算
已知若干线段 找一点 连接到这线段上某一点 使得距离和最小
连续变化 用大步长确定范围 小步长确定位置
若干活动 知道起始时间 求不冲突活动的最大个数
按结束时间排序 然后如果m在i之后开始 j前结束 的结束时间最小的 那么m必选 i m之间没有其他活动
若干活动 知道起始时间 求安排所有活动的最少礼堂数
将开始和结束时间并在一个表里排序 开始的时候找到一个空闲的礼堂插入 如果未使用过 礼堂数+1 结束的时候把该礼堂设置为空闲 放入空闲礼堂对首
序列AB 要求Pi(ai^bi)最大的排序方案
降序排列 bi>=bj ai>=aj ai^(bi-bj) >= aj^(bi-bj) ai^bi*aj^bj >= ai^bj*aj^bi
文章来源: http://thunderfyc.wordpress.com.cn
