基础DP的一些知识总结(未完成)

DP的思路:

①DAG上的最长(短)路问题

有两种状态转移,

第一个就是从其他状态获得状态F[i],第二个就是从F[i]得到其他独立的状态,这里一定要是独立的,不然后面更新的时候会遗漏。这两种状态各有优劣,具体题目具体分析。

①完全背包的变种 HDU1114

这里一定要能组合到S。白皮书60页。

②免费馅饼HDU1176

地图中先赋值,然后再枚举状态即可

③最长公共子序列的变种

加强的就是最长的k个字母连续的公共子序列

上一篇:oracle数据类型


下一篇:linux的文件权限小结