「AHOI2014/JSOI2014」骑士游戏

标签：code   operator   continue   初始   mes   etc   oid   define   tps   

「AHOI2014/JSOI2014」骑士游戏

传送门
考虑 \(\text{DP}\)。
设 \(dp_i\) 表示灭种（雾）一只编号为 \(i\) 的怪物的代价。
那么转移显然是：
\[dp_i = \min(K_i, S_i + \sum_{j = 1}^{R_i} dp_{v_j})\]
但是我们会发现这个东西是有后效性的。。。
所以我们会想要用建图然后跑一个最短路什么的来搞。。。
于是我们观察到上面那个 \(\text{DP}\) 式子中，\(dp_i\) 如果用后面那一项来转移，显然会有 \(dp_{v_j} 。
这提示我们，为了消除后效性，可以对 \(dp\) 值排序。
准确的说就是开一个堆来搞，每个点初始的 \(dp\) 值都是消灭它的魔法消耗，然后优先更新较小的 \(dp\) 值，
毕竟我们对于魔法消耗最小的怪物肯定是直接消灭（因为你到头来都要干死它何必生出一些魔法消耗更高的嘞）
然后我们建图方式就是反着来，如果 \(i\) 会生出 \(j\)，那么连边 \(j \to i\)，然后我们就跑一个长的有点像 \(\text{Dijkstra}\) 的 \(\text{DP}\) 就好了。
参考代码：

#include 
#include 
#define rg register
#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)
using namespace std;
template  inline void read(T& s) {
    s = 0; int f = 0; char c = getchar();
    while ('0' > c || c > '9') f |= c == '-', c = getchar();
    while ('0'  y.val; }

priority_queue  Q;

int main() {
#ifndef ONLINE_JUDGE
    file("cpp");
#endif
    read(n);
    for (rg int i = 1; i  s[v] && !--r[v])
                dp[v] = s[v], Q.push((node) { v, dp[v] });
        }
    }
    printf("%lld\n", dp[1]);
    return 0;
}

「AHOI2014/JSOI2014」骑士游戏

标签：code   operator   continue   初始   mes   etc   oid   define   tps   

原文地址：https://www.cnblogs.com/zsbzsb/p/12254210.html