当前位置: 代码迷 >> 综合 >> 暴力的优化方法总结
  详细解决方案

暴力的优化方法总结

热度:67   发布时间:2023-09-23 04:48:36.0

暴力就是所有解都试一下,找出最优解


1.贪心

一些显而易见的不可能的解事先排除

数组排序啊。事先处理一些数据什么的


2.枚举的顺序(定一个量,枚举另一个)

一开始枚举不同的量的时间复杂度可能不一样

UVa 10125 Sumsets 枚举4个数,变为枚举2个数

UVa 10391 Compound Words 枚举两个单词拼成一个,不如枚举一个单词拆成两个


3.二分

二分查找答案,问题就转化为该答案是不是合法


4.数形结合,单调队列优化,斜率优化

LA 4726 Average *


5.维护信息,而不是重新计算

比如 事先求好前缀和,就不用再次算

由之前递推到下一个;充分利用已知信息;DP


6.中途相遇法

有点像 DBFS感觉


7.DFS的最优性剪枝,可行性剪枝....,A*什么的




  相关解决方案