自动搬运

查看原文

来自洛谷，原作者为

	lwyz123 **

搬运于2025-08-24 21:52:40，当前版本为作者最后更新于2019-10-15 21:17:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

最短路作为广为人知的算法，肯定不可能考模板的啦（毒奶一口）

今天看到p3786 萃香抱西瓜：

前两天的胡策题，(毒瘤出题人,根本不理解！！！）

在一天半之后，我终于" 做 "掉了他;

其实呢这个题并不是多么毒瘤，看到h ,w 只有5！！！, 需要杀的人小于10个！！

你有什么想法呢！！

状压就完了

主题思路： 状压+spfa；

关键变量：

dis[x][y][t][S] //前三维不多说最后一维记状态； 有了这个！！ 你也可以想到vis数组的魔改版； vis[x][y][t][s];

这个思路呢你可以去做做 （bfs好题p1301 魔鬼之城）

空间够大就用空间来换时间!!!

并且还能保证你答案的正确性！！

血赚不亏；

剩下的需要一个map[x][y][t] 来记录点

注意不能抱走的西瓜 我们可以定义一个wm_big随便开一个值只要不会和小西瓜重复

剩下的可以抱走的西瓜就可以按照输入的顺序来编号cnt

然后map[x][y][t]=(1<<(cnt-1))

注意位运算的顺序

剩下的就可以根据楼上神仙们的题解代码来理解了 我就不贴了；