暑期集训 DP 篇

经常犯的愚蠢错误

• DP 一定要记得初始化的问题,不然会出一些(mmp)奇奇怪怪的错误.
• DP 很多时候是可以省维数的. (用滚动数组)
• 有时用memset初始化会超时, 把它改成for循环却又能过...真是非常奇妙
• 交题前务必记得把freopen给注释掉, 把自己检查所用的printf也都注释掉, 不要白白浪费提交次数.
• 有时用int 可能会超, 要改成long long, 但long long 和int 之间的关系又好像十分奇妙, 有时打印时不注意也会出些奇奇怪怪的错误, 比如上次打cf 839 C 就因为这个调了半天, 假如自己算了是肯定在int 范围内就别用long long 了, 麻烦.
• 不过有的题目又非常坑. 题意描述里说好了是给int , 不用lld来读又会出错.
• 有的完全背包问题 你看着像贪心, 其实是DP.
• 有的状态压缩的DP题, 你看着像搜索, 又寻思打DFS会TLE, 其实是DP.
• 有的时候一个关键词漏了就会觉得这个题爆难, 所以觉得没法做的时候再认真读一遍题. 比如: HDU 1069 里面每种砖块的数量是无限的.
• 状态转移方程要想想是不是对的.
• 要注意循环内部变量修改的顺序.
• 不要写麻烦的逻辑判断, 越麻烦越容易出错, 越简单的代码往往越不容易出错. The simpler, the better.
• 注意假如一个数组读进来以后还要在后面加一些东西, 那么开数组之前就要考虑大小问题. (这种RE错误我犯了好多了....)