DAG上dp思想DAG上DP的思想
DAG上DP的思想在下最近刷了几道DAG图上dp的题目。要提到的第一道是NOIP原题《最优贸易》。这是一个缩点后带点权的DAG上dp,它同时规定了起点和终点。第二道是洛谷上的NOI导刊题目《最长路》,一个裸的DAG上dp,也同时规定了起点和终点。这是为什么?我想了一下。首先spfa跑最长路,它得保证是一张DAG。否则你可以在一个正权环上无限的松弛下去。其次考虑一下最长路的DAG拓扑序d...