Mayflyyh
Mayflyyh
MayFlyyh's Blog
BZOJ 3875 [Ahoi2014&Jsoi2014]骑士游戏

Description
【故事背景】
长期的宅男生活中,JYY又挖掘出了一款RPG游戏。在这个游戏中JYY会
扮演一个英勇的骑士,用他手中的长剑去杀死入侵村庄的怪兽。
【问题描述】
在这个游戏中,JYY一共有两种攻击方式,一种是普通攻击,一种是法术攻
击。两种攻击方式都会消耗JYY一些体力。采用普通攻击进攻怪兽并不能把怪兽彻底杀死,怪兽的尸体可以变出其他一些新的怪兽,注意一个怪兽可能经过若干次普通攻击后变回一个或更多同样的怪兽;而采用法术攻击则可以彻底将一个怪兽杀死。当然了,一般来说,相比普通攻击,法术攻击会消耗更多的体力值(但由于游戏系统bug,并不保证这一点)。
游戏世界中一共有N种不同的怪兽,分别由1到N编号,现在1号怪兽入
侵村庄了,JYY想知道,最少花费多少体力值才能将所有村庄中的怪兽全部杀死呢?
Input
第一行包含一个整数N。
接下来N行,每行描述一个怪兽的信息;
其中第i行包含若干个整数,前三个整数为Si,Ki和Ri,表示对于i号怪兽,
普通攻击需要消耗Si的体力,法术攻击需要消耗Ki的体力,同时i号怪兽死亡后会产生Ri个新的怪兽。表示一个新出现的怪兽编号。同一编号的怪兽可以出现多个。
Output
输出一行一个整数,表示最少需要的体力值。

HINT
【样例说明】

首先用消耗4点体力用普通攻击,然后出现的怪兽编号是2,2和3。花费

10点体力用法术攻击杀死两个编号为2的怪兽。剩下3号怪兽花费1点体力进

行普通攻击。此时村庄里的怪兽编号是2和4。最后花费11点体力用法术攻击

将这两只怪兽彻底杀死。一共花费的体力是4+5+5+1+5+6=26。

【数据范围】

2<=N<=210^5,1<=Ri,Sigma(Ri)<=10^6,1<=Ki,Si<=510^14


设物理攻击为Pi,魔法攻击为Mi,最小杀死花费为Si

Si=min(Mi,Pi+sigma{S[son]});

用spfa (Dijsktra) 处理 后效性、环状依赖关系的dp转移

先把所有点放到队列里

然后一个点出队,先统计自己依赖的,如果自己的S有变动在把依赖自己的放到队列里。

因为M和P都是正的,所以只会有正环,套着套着就稳定了。

#include<bits/stdc++.h>
#define ll long long
const int N = 1e5*2+1e2;
int last[N],last2[N];
int cnt,n;bool v[N];
ll P[N],M[N];
struct edge{
    int next,to;
}e[N*10];
void add(int a,int b){cnt++;e[cnt].next=last[a],last[a]=cnt;e[cnt].to=b;}
void add2(int a,int b){cnt++;e[cnt].to=b,e[cnt].next=last2[a],last2[a]=cnt;}
void bfs(){
    std::queue<int> q;
    for(int i=1;i<=n;++i){q.push(i),v[i]=1;}
    while(!q.empty()){
        int x=q.front();q.pop();v[x]=0;
        ll s=P[x];
        for(int i=last[x];i;i=e[i].next){s+=M[e[i].to];}
        if(s>M[x]) continue;
        M[x]=s;
        for(int i=last2[x];i;i=e[i].next){
            if(!v[e[i].to]){
                v[e[i].to]=1;
                q.push(e[i].to);
            }
        }
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        int x;
        scanf("%lld %lld %d",&P[i],&M[i],&x);
        while(x--){
            int b;scanf("%d",&b);
            add(i,b);
            add2(b,i);
        }
    }
    bfs();
    printf("%lld",M[1]);
    return 0;
}
本文链接:http://www.mayflyyh.com/archives/345
知识共享许可协议
本文采用CC BY-NC-SA 3.0进行许可。
首页      DP      BZOJ 3875 [Ahoi2014&Jsoi2014]骑士游戏
http://0.gravatar.com/avatar/6cc3a2831375e487976e09c80dfcb52e?s=256&d=monsterid&r=g

MayFlyyh

文章作者

Oier

发表评论

textsms
account_circle
email

MayFlyyh's Blog

BZOJ 3875 [Ahoi2014&Jsoi2014]骑士游戏
Description 【故事背景】 长期的宅男生活中,JYY又挖掘出了一款RPG游戏。在这个游戏中JYY会 扮演一个英勇的骑士,用他手中的长剑去杀死入侵村庄的怪兽。 【问题描述】 在这个…
扫描二维码继续阅读
2018-09-20