我是用SPFA做的,其中每个节点是一个三元组 (x,y,c),其中:
- x 表示横坐标
- y iangt坐状态angt坐标;
- c 表示颜色(c∈[0,1])
然后,如果我当前的节点有颜色(假设当前节点为 u,其对应的三元组为 (u.x,u.y,u.z)),而我要扩展出来的节点为 (x,y,c),正常情况下我应该枚举 c 为 0 和 1 两种情况进行扩展。(我这样做也AC了)。
但是我这里有一个 贪心 的想法,就是设我扩展出来的状态的颜色 c 直接等于 u.c,这样我当前的转移的花费为 2,相比另一种情况(花费 2+1=3)来说,我此时腾出了 1 块钱可以在接下来用。
但是我这么做就只拿了 70 分,请问我这种贪心策略有问题吗?