首页 > 光玉小镇
开通博客写题解
头像 我想一发AC唔
发表于 2020-08-25 09:11:41
题意 给定一个字符串的图，让你处理一个图的问题。给定不超过15个点的图，让你求从起点遍历完所有点并回到起点的最小花费。题解 我们可以把s和t抽出来建图，然后跑最短路建立点之间的关系。然后我们用状压dp求解遍历完所有点的花费，最后加上(点数-1)*t，即为整个的花费。代码 #include<bi 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 璃墨韵
发表于 2020-08-25 15:00:17
看到且‘T’的数目大于等于1并且小于等于15，考虑状压dp可以记录当前修理的状态和最后所在的电线杆，设f[i][j]表示当前集合为i且最后所在的电线杆为j的代价，先预处理家与电线杆之间的距离和两两电线杆之间的距离，并转移即可 #include<algorithm> #include< 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 Meul
发表于 2020-09-17 15:56:46
NC6874C-光玉小镇 求从走完所有再回到所需的最小时间为多少，每经过一次T时间需要停，走一步的时间是.若不能走完所有的，输出，否则输出所需的最小时间。 Solution 状压DP+BFS难点：有多个，我们需要先确定的顺序。 注意到的范围，我们从状压DP的经典题TSP问题中得到启示，我们可以 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 bai_qi
发表于 2020-09-07 17:18:08
题目描述经历过与妻儿生离死别的牛牛，选择成为一名电工，过上平淡的日子。牛牛每天的工作是从家里出发，修理完小镇上所有坏掉的电线杆，然后回家和家人团聚。已知小镇是个n\times mn×m的区域，每块格子的类型有以下几种： ‘.’：表示该地点为空地。 ‘#’：表示该地点正在施工，牛牛无法移动到该地点。 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”