TravellingPurchasingMan

作者：闫书弈

关键词：动态规划 状压

题目简述

有n个商店，通过m条双向道路连接，通过第i条道路需要leni的时间。

你可以在编号为0至p-1的商店里购买物品。为了在第i号商店购买物品，你需要在时刻[li,ri]开启一次购买(包括时刻li和时刻ri)，持续ti个时刻。你只能在每个商店购买一次物品。

在时刻0你位于编号为n-1的商店，你需要求出你最多能购买多少物品。

1<=n,m<=50，1<=p<=min(16,n)，1<=leni<=604800，0<=li<ri<=604800，1<=ti<=604800。

解法

先用floyd求出商店间的最短路，然后状压dp。dp时记录已经在哪些商店买好东西，当前在哪个商店，枚举上一个商店转移过来即可。

时间复杂度O(n^3+2^p*p^2)。