行使普攻进攻怪兽并无法把怪兽通透到底杀死,而选择法术攻击则足以深透将三个怪兽杀死

Sample Input

4
4 27 3 2 3 2
3 5 1 2
1 13 2 4 2
5 6 1 2

3875: [Ahoi2014]骑兵游戏

Time Limit: 30
Sec  Memory Limit: 256 MB

Sample Output

26

Description

 【传说背景】

悠久的丑挫穷子活中,JYY又开采出了一款CAG游戏。在那个娱乐中JYY会

装扮三个义不容辞的铁骑,用他手中的长剑去杀死侵袭村庄的怪兽。

【难题讲述】

在那一个游戏中,JYY一共有二种攻击形式,一种是普通的攻击,1种是法术攻击。三种攻击格局都会消耗JYY一些体力。采取普攻进攻怪兽并不可能把怪兽深透杀死,怪兽的尸体能够变出任何部分新的怪兽,注意3个怪兽大概因此多少次普通的攻击后变回三个或越来越多一致的怪兽;而接纳法术攻击则能够深透将一个怪兽杀死。当然了,一般的话,相比较普通的攻击,法术攻击会消耗更加多的体力值(但出于玩耍系统bug,并不有限支撑那或多或少)。

玩耍世界香港中华总商会计有N种分歧的怪兽,分别由1到N编号,未来1号怪兽凌犯村庄了,JYY想明白,最少费用稍微体力值技能将富有村庄中的怪兽全体干掉呢?

HINT

【样例表明】

先是用消耗四点体力用普攻,然后出现的怪兽编号是二,二和叁。

消费十点体力用法术攻击杀死五个号码为二的怪兽。

剩余三号怪兽费用1点体力举行普通的攻击。

此刻村子里的怪兽编号是贰和四。

末尾成本1一点体力用法术攻击将那七只怪兽彻底杀死。

总共消费的体力是四+5+5+1+5+陆=二陆。

【数据范围】

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

 

 

  那确实是一道很妙的题,反正自个儿是没做出来的。

  困扰在”3个怪被砍死社长出一堆分歧的怪”那么些题目上,难道怪物基因都以同1的怎么跑最短路啊。

  去互连网看了壹波题解开掘都讲的很少,就好像是因为这题太水?智力障碍选手请太早弃疗。

  假如未有环出现,对它是四个DAG,正是一个很水的DP题了,反向拓扑一下。

  然后今后有环了。有环就会有啥样吗?有后效性。DP是不可能消除有后效性的难题的。

  不过SPFA能够。SPFA正是一点一滴未有管后效性的算法(所以很轻松被卡?)。

  设把怪净化掉的细微花费是f。那么就有:
f[i]=min(K[i],S[i]+Σf[R]);

  所以3个钱物被更新恐怕会变成四驱的更新。

  所以把它的先驱扔进队列直到队列为空输出f[1]是什么算法啊啊啊啊!

  咳咳。所以具体落到实处步骤正是那般:

  把全部的点的f赋为K[i]并投入队列。

  总计队首的f’。借使比当下过得硬,就更新并进入全体前任。

  直到队列空。

  其实自身很恐怖这一个东西的复杂度,不过正是过了…

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#include    <complex>
#include    <stack>
#define LL long long int
#define dob double
using namespace std;

const int N = 200010;
const int M = 1000010;
struct Node{int to,next;}E[M];
int head[N],tot,n,In[N],R[N];
LL S[N],f[N],K[N];
vector<int>G[N];

int gi()
{
  int x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}

LL gL()
{
  LL x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}

inline void link(int u,int v){
  E[++tot]=(Node){v,head[u]};
  head[u]=tot;
}

inline void SPFA()
{
  queue<int>Q;for(int i=1;i<=n;++i)Q.push(In[i]=i);
  while(!Q.empty()){
    int x=Q.front();Q.pop();In[x]=0;LL sum=S[x];
    for(int i=0;i<R[x];++i)sum+=f[G[x][i]];
    if(sum>=f[x])continue;f[x]=sum;
    for(int e=head[x];e;e=E[e].next)
      if(!In[E[e].to])Q.push(E[e].to),In[E[e].to]=1;
  }
}

int main()
{
  n=gi();
  for(int i=1;i<=n;++i){
    S[i]=gL();K[i]=gL();R[i]=gi();
    for(int j=1;j<=R[i];++j){
      int r=gi();
      link(r,i);G[i].push_back(r);
    }
    f[i]=K[i];
  }
  SPFA();
  printf("%lld\n",f[1]);
  return 0;
}

  

Sample Input

4
4 27 3 2 3 2
3 5 1 2
1 13 2 4 2
5 6 1 2

Output

 输出一行1个整数,表示最少须求的体力值。

Sample Output

26

HINT

【样例表达】

率先用消耗4点体力用普攻,然后出现的怪兽编号是二,二和叁。开销十点体力用法术攻击杀死三个号码为二的怪兽。剩下三号怪兽开销一点体力举行普通的攻击。此时村子里的怪兽编号是二和四。最终开支11点体力用法术攻击将那八只怪兽彻底杀死。壹共消费的体力是四+5+5+壹+伍+陆=二陆。

【数据范围】

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

 

正解:$spfa$。

相遇那种有后效性的$dp$一般能够用$spfa$消除。

大家假使根据$spfa$的思路,假若当前点被更新了,就用它去松弛别的点。

诸如此类遵照最短路的思维来更新,是迟早能够获得最优解的。

 

 1 //It is made by wfj_2048~
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <cstring>
 5 #include <cstdlib>
 6 #include <cstdio>
 7 #include <vector>
 8 #include <cmath>
 9 #include <queue>
10 #include <stack>
11 #include <map>
12 #include <set>
13 #define sz (2000010)
14 #define N (200010)
15 #define il inline
16 #define RG register
17 #define ll long long
18 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
19 
20 using namespace std;
21 
22 vector <int> g1[N],g2[N];
23 queue <int> Q;
24 
25 ll s[N],k[N],f[N];
26 int vis[N],n;
27 
28 il ll gi(){
29     RG ll x=0,q=1; RG char ch=getchar();
30     while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
31     if (ch=='-') q=-1,ch=getchar();
32     while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar();
33     return q*x;
34 }
35 
36 il void work(){
37     n=gi();
38     for (RG int i=1,r;i<=n;++i){
39     s[i]=gi(),k[i]=gi(),r=gi();
40     for (RG int j=1,x;j<=r;++j)
41         x=gi(),g1[i].push_back(x),g2[x].push_back(i);
42     }
43     for (RG int i=1;i<=n;++i) Q.push(i),vis[i]=1,f[i]=k[i];
44     while (!Q.empty()){
45     RG int x=Q.front(); Q.pop(); RG ll sum=s[x]; vis[x]=0;
46     for (RG int i=0;i<g1[x].size();++i) sum+=f[g1[x][i]];
47     if (f[x]<=sum) continue; f[x]=sum;
48     for (RG int i=0,v;i<g2[x].size();++i){
49         v=g2[x][i];
50         if (!vis[v]) Q.push(v),vis[v]=1;
51     }
52     }
53     printf("%lld\n",f[1]); return;
54 }
55 
56 int main(){
57     File("knight");
58     work();
59     return 0;
60 }

 

3875: [Ahoi2014]铁骑自行车旅游戏

Time Limit: 30
Sec  Memory Limit: 256 MB

Description

 【有趣的事背景】

长此以后的宅汉子活中,JYY又开采出了一款RAC游戏。在那几个游戏中JYY会

扮作八个义无反顾的骑士,用他手中的长剑去杀死侵犯村庄的怪兽。

【难点讲述】

在这一个游乐中,JYY一共有三种攻击格局,1种是普攻,一种是法术攻击。二种攻击格局都会消耗JYY一些体力。选拔普攻进攻怪兽并不可能把怪兽通透到底杀死,怪兽的遗体能够变出其它部分新的怪兽,注意四个怪兽大概由此多少次普攻后变回2个或越来越多一致的怪兽;而选拔法术攻击则足以透顶将1个怪兽杀死。当然了,一般的话,相比较普攻,法术攻击会消耗更加多的体力值(但由于玩耍系统bug,并不有限支撑那点)。

玩耍世界中计算有N种分歧的怪兽,分别由1到N编号,未来一号怪兽侵略村庄了,JYY想理解,最少开销稍微体力值能力将持有村庄中的怪兽全体干掉呢?

Output

 输出壹行2个平头,表示最少须求的体力值。

Sample Output

26

Input

率先行蕴含1个整数N。

接下去N行,每行描述三个怪兽的消息;

在那之中第i行李包裹蕴若干个整数,前三个整数为Si,Ki和Ri,表示对于i号怪兽,

普通的攻击要求消耗Si的体力,法术攻击需求消耗Ki的体力,同时i号怪兽谢世后会发生Ri个新的怪兽。表示1个新面世的怪兽编号。同一编号的怪兽能够出现多少个。

Description

 【典故背景】

长时间的屌丝人活中,JYY又发掘出了一款ACT类游戏。在那些游乐中JYY会扮演多少个敢于的铁骑,用他手中的长剑去杀死侵犯村庄的怪兽。

【难点讲述】

在这么些娱乐中,JYY一共有三种攻击方式,1种是普通的攻击,一种是法术攻击。二种攻击方式都会消耗JYY一些体力。选用普通的攻击进攻怪兽并不能把怪兽通透到底杀死,怪兽的尸体能够变出任何部分新的怪兽,注意八个怪兽大概由此多少次普攻后变回1个或愈来愈多一致的怪兽;而采取法术攻击则足以彻底将三个怪兽杀死。当然了,一般的话,相比较普通的攻击,法术攻击会消耗更多的体力值(但出于玩耍系统bug,并不有限支撑那点)。

打闹世界中壹共有N种分歧的怪兽,分别由一到N编号,今后1号怪兽凌犯村庄了,JYY想明白,最少费用稍微体力值才具将持有村庄中的怪兽全体杀死呢?

HINT

【样例表明】

先是用消耗四点体力用普通的攻击,然后出现的怪兽编号是二,2和三。

消费十点体力用法术攻击杀死三个号码为2的怪兽。

剩余三号怪兽费用1点体力进行普攻。

那会儿村子里的怪兽编号是二和四。

终极开销1一点体力用法术攻击将那五只怪兽深透杀死。

共计消费的体力是四+伍+伍+一+5+陆=二六。

【数据范围】

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

 

 

  那的确是壹道很妙的题,反正本人是没做出来的。

  干扰在”三个怪被砍死团体带头人出一群不一致的怪”这几个主题素材上,难道怪物基因都是如出一辙的怎么跑最短路啊。

  去网络看了一波题解开掘都讲的很少,仿佛是因为那题太水?智力障碍选手请太早弃疗。

  即便未有环出现,对它是贰个DAG,正是三个很水的DP题了,反向拓扑一下。

  然后以后有环了。有环就会有何样吗?有后效性。DP是不可能化解有后效性的标题标。

  不过SPFA能够。SPFA正是一心未有管后效性的算法(所以很轻便被卡?)。

  设把怪净化掉的纤维成本是f。那么就有:
f[i]=min(K[i],S[i]+Σf[R]);

  所以二个钱物被更新恐怕会导致四驱的更新。

  所以把它的前任扔进队列直到队列为空输出f[1]是什么样算法啊啊啊啊!

  咳咳。所以实际得以落成步骤正是那样:

  把装有的点的f赋为K[i]并参加队列。

  总计队首的f’。借使比近年来卓越,就创新并投入全部前任。

  直到队列空。

  其实小编很恐怖那些事物的复杂度,可是正是过了…

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#include    <complex>
#include    <stack>
#define LL long long int
#define dob double
using namespace std;

const int N = 200010;
const int M = 1000010;
struct Node{int to,next;}E[M];
int head[N],tot,n,In[N],R[N];
LL S[N],f[N],K[N];
vector<int>G[N];

int gi()
{
  int x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}

LL gL()
{
  LL x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}

inline void link(int u,int v){
  E[++tot]=(Node){v,head[u]};
  head[u]=tot;
}

inline void SPFA()
{
  queue<int>Q;for(int i=1;i<=n;++i)Q.push(In[i]=i);
  while(!Q.empty()){
    int x=Q.front();Q.pop();In[x]=0;LL sum=S[x];
    for(int i=0;i<R[x];++i)sum+=f[G[x][i]];
    if(sum>=f[x])continue;f[x]=sum;
    for(int e=head[x];e;e=E[e].next)
      if(!In[E[e].to])Q.push(E[e].to),In[E[e].to]=1;
  }
}

int main()
{
  n=gi();
  for(int i=1;i<=n;++i){
    S[i]=gL();K[i]=gL();R[i]=gi();
    for(int j=1;j<=R[i];++j){
      int r=gi();
      link(r,i);G[i].push_back(r);
    }
    f[i]=K[i];
  }
  SPFA();
  printf("%lld\n",f[1]);
  return 0;
}

  

Output

 输出壹行三个平头,表示最少须求的体力值。

Input

率先行李包裹涵2个整数N。

接下去N行,每行描述1个怪兽的新闻;

在那之中第i行李包裹罗若干个整数,前多个整数为Si,Ki和Ri,表示对于i号怪兽,

普通的攻击须求消耗Si的体力,法术攻击须要消耗Ki的体力,同时i号怪兽去世后会产生Ri个新的怪兽。表示二个新出现的怪兽编号。同一编号的怪兽能够出现三个。

Input

第三行包蕴一个整数N。

接下去N行,每行描述三个怪兽的新闻;

中间第i行李包裹括若干个整数,前三个整数为Si,Ki和Ri,表示对此i号怪兽,

普攻必要消耗Si的体力,法术攻击须要消耗Ki的体力,同时i号怪兽与世长辞后会发生Ri个新的怪兽。表示贰个新面世的怪兽编号。同一编号的怪兽能够出现八个。

Sample Input

4
4 27 3 2 3 2
3 5 1 2
1 13 2 4 2
5 6 1 2

相关文章