UVALive 8149 – SWERC2017E – Ingredients

题面链接:UVALive – 8149 / Gym – 101635E

题目保证这是一张有向无环图。先用SPFA/Dijsktra求出做出每种菜的最小消费,松弛的时候注意判断消费相等的情况下要取声望的最大值;接着就是在这个DAG上做动态规划(0-1背包),用滚动数组维护。

 

说点什么

avatar
50
  Subscribe  
提醒