JYY一共有两种攻击方式,一种是普通攻击,一种是法术攻击

两种攻击方式都会消耗JYY一些体力。采用普通攻击进攻怪兽并不能把怪兽彻底杀死
怪兽的尸体可以变出其他一些新的怪兽,注意一个怪兽可能经过若干次普通攻击后变回一个或更多同样的怪兽
而采用法术攻击则可以彻底将一个怪兽杀死

游戏世界中一共有N种不同的怪兽,分别由1到N编号
在1号怪兽入侵村庄了,JYY想知道,最少花费多少体力值才能将所有村庄中的怪兽全部杀死呢

这真的是一道好题啊……
一开始想的是,使用普通攻击杀死一个怪物,产生了分裂体\(a_1\)~\(a_x\)
那么\(ans[i]=min(f[i]+ans[a1]+...+ans[an],g[i])\)
乱写的式子,就是说杀死其本体分裂体的最小价值与直接杀死本体的价值取min

但是这样一直递归下去求解的话……好像没有初始位置来着?
分裂关系可能成环,那dp就废了

仔细思索后发现居然要用spfa建模?


怎么又下课了

明天继续写
(笑

01-09 04:37