做到F心态崩了,自然不会去做G.
F
考虑最终路径一定是这样的 1到x节点 在x处攒够路费再到n.
后者可以通过从n跑dij来求最短路。
考虑前者 需要求从1~x的最小代价。
一个初始的想法是直接从1开始跑dij存一些状态。
进一步的可以发现这是从1到n最小代价的子问题。重复上述过程即可。
考虑演出会收入w ,一个转移 x->y 如果wx>wy 那么这个转移对到n来说没有意义因为x一定比y优.
对w进行排序就可以有序dp了。
因为需要求很多点之间的最短路可以直接floyd.
E
可以简化每一个唱片。
然后发现每一个唱片中的最大值影响唱片之间的关系。对其从小到大排序。
设fi表示到第i个唱片的最大长度。
枚举第i歌唱从哪开始接上再枚举决策j。
树状数组优化决策j的寻找即可。
D
将a,b放一起排序枚举a,b中的最大值。
然后寻找一个次大值并且满足集合的并为全集即可。
注意特殊情况次大值和最大值的id不能相同。
C
之间构造i<<8|j即可。
B
贪心的放即可。
A
直接输出。