“默认填充的颜色和当前格子颜色相同”的这种贪心策略是否有问题?
查看原帖
“默认填充的颜色和当前格子颜色相同”的这种贪心策略是否有问题?
291976
quanjun楼主2020/5/30 15:32

我是用SPFA做的,其中每个节点是一个三元组 (x,y,c)(x,y,c),其中:

  • xx 表示横坐标
  • yy iangt坐状态angt坐标;
  • cc 表示颜色(c[0,1]c \in [0,1]

然后,如果我当前的节点有颜色(假设当前节点为 uu,其对应的三元组为 (u.x,u.y,u.z)(u.x, u.y, u.z)),而我要扩展出来的节点为 (x,y,c)(x, y, c),正常情况下我应该枚举 cc0011 两种情况进行扩展。(我这样做也AC了)。

但是我这里有一个 贪心 的想法,就是设我扩展出来的状态的颜色 cc 直接等于 u.cu.c,这样我当前的转移的花费为 22,相比另一种情况(花费 2+1=32+1=3)来说,我此时腾出了 11 块钱可以在接下来用。

但是我这么做就只拿了 70 分,请问我这种贪心策略有问题吗?

2020/5/30 15:32
加载中...