Fork me on GitHub

ZROJ2018D6T1--萌新拆塔

发表于 | | 阅读次数:
字数统计: 2,105

传送门：ZROJ2018D6T1—萌新拆塔

注：杜老师出题~~~

题面：

  • 作为一场自闭模拟赛，需要一道10k模拟加玄学剪枝题。
  • 在魔塔这个游戏中，勇士有四个数值，血量，攻击，防御和魔防。怪物也有三个数值，血量，攻击和防御。勇士和怪物攻击方式一般是这样的，双方轮流攻击，每回合造成自己攻击减去对方防御的伤害，如果自己的攻击比对方的防御低，那么无法对对方造成伤害。如果怪物血量变得小于等于0，那么怪物死亡，勇士获胜。如果勇士的攻击不超过怪物的防御，那么无法战斗。在一场战斗后，如果怪兽造成的总伤害超过了自己的魔防，那么消耗的血量为总伤害减去自己的魔防值，否则伤害为0。勇士必须保证战斗之后剩余的血量大于0。
  • 一般来说，都是勇士先攻击。但是怪物有一些特殊属性：
  • 先攻：第一个回合由怪物先攻击。
  • 魔攻：怪物会无视勇士的防御，你可以认为在战斗的时候勇士的防御为0。
  • 二连击：怪物每回合攻击两次。
  • 模仿：怪物的攻防与勇士的攻防相同。
  • 这四个特殊属性都是可以任意叠加的。
  • 这个魔塔里面有n个怪，每个怪后面都守着一个宝石，每个宝石都能对血量，攻击，防御和魔防这些数值有所增益。同时打怪之间有一些先后顺序，比如说如果怪v被怪u挡住了，那么我们只能先打u再打v。所以我们会有k条规则，表示u这个怪必须在v之前打。
  • 你可以需要按一定顺序去清怪和吃宝石，吃宝石之前要求守着这个宝石的怪被杀死。
  • 请问杀完所有的怪剩下的最多能剩多少血量。

输入格式:

  • 第一行一个整数T，表示数据组数。
  • 每组数据第一行四个整数，表示$h,a,d,m$，表示勇士的初始血量，攻击，防御与魔防。$(1≤h≤10^9,1≤a,d≤10^5,0≤m≤10^5)$
  • 接下来一行一个数字n，表示怪的数量。
  • 接下来n行，每行八个数字，表示$H,A,D,S,ap,dp,mp,hp$，表示怪物的血量，攻击，防御，属性，以及怪物守的宝石能增加的攻击，防御，魔防和血量。 $(1≤H,A,D≤10^5,0≤S≤15,0≤ap,dp,mp≤10^4,1≤hp≤10^9)$
  • 怪物的属性由二进制表示，如果有先攻属性，那么S增加1，魔攻增加2，二连击增加4，模仿增加8。
  • 接下来一行一个整数k，表示有k条规则。接下来k行，每行两个正整数$u,v(1≤u<v≤n)$，表示怪u必须在怪v之前杀死。

输出格式

  • 对于每组数据输出一行，表示杀完所有的怪剩下的最多血量。如果无法清完所有怪，那么输出−1。

样例:

  • 样例输入:
    1
    20 2 2 0
    10
    2 2 0 0 2 0 0 80
    18 8 0 0 0 0 0 20
    40 6 1 0 2 0 0 40
    42 7 3 0 1 0 0 40
    10 10 5 0 0 2 0 40
    25 5 0 0 0 0 0 20
    35 4 1 0 0 1 0 20
    60 7 2 0 1 1 0 40
    32 8 2 0 0 0 0 60
    160 15 0 0 0 0 0 0
    9
    1 2
    2 3
    1 4
    4 5
    1 6
    6 7
    6 8
    7 9
    4 10

  • 样例输出:
    -1

限制与规定：

  • 对于 20% 的数据，有 1≤n≤5,k=0，所有怪物没有特殊属性。
  • 对于 40% 的数据，有 1≤n≤8,k=0，所有怪物没有特殊属性。
  • 对于另外 20% 的数据，有 1≤n≤14,k≤100，所有怪物没有特殊属性。
  • 对于另外 20% 的数据，有 1≤n≤8,k≤100。
  • 对于 100% 的数据，有 1≤n≤14,k≤100,T≤10。
  • 时间限制：10s
  • 空间限制：512MB

解释：

  • 关于魔防可以认为打完一个怪总伤害会减去魔防的值，也可以理解成每次打怪前你有一个血量为魔防值的护盾，怪物会优先扣护盾的血量。
  • 比如说你的攻击是15，防御是5，魔防是7，怪物血量是20，攻击是20，防御是5，没有特殊属性。
  • 那么你可以在2轮杀死怪物，怪物会攻击你1轮。你打这个怪受到的伤害为max(15−7,0)。
  • 你每次可以选择打一个不违反限制的怪或者吃一个不违反限制的宝石。
  • 样例1只要按顺序打怪并且吃宝石即可。
  • 两个人轮流攻击，我们记A为勇士，B为怪物。
  • 那么先攻的攻击顺序为BABABA…
  • 二连击的攻击顺序为ABBABBABB…

吐槽&题解：

  • 古老的魔塔游戏2333
  • 跟10k大模拟没有毛线关系（不愧是传说中的毒瘤出题人）
  • 三进制状压。。。（看到数据范围想到二进制状压emmm）
  • 第i位为0表示没打第i位怪，1表示打了怪没吃水晶（Q：为什么会不吃水晶呢？A：因为有模仿怪呀！），2表示打了怪吃了水晶。
  • 因为答案是要求最大血量，那么我们就用f[i]来表示i这个状态最大的血量，然后预处理出各个状态的攻击，防御，魔防。
  • 转移的话，第i只怪的位置如果要从0->1，则先判断在这只怪之前必打的怪打了没有，然后如果S（S为以当前状态k的属性打这个怪后的血量）大于要更新的状态$f[k+3^{i-1}]$，那就更新。
  • 而如果要从1->2，则只要$f[k+3^{i-1}]=max(f[k+3^{i-1}],f[k]+hp[i])$,因为其它属性已经预处理好了。
  • 至于打怪操作和怪的特殊属性，大力模拟就好了。。。

贴个代码。。。暴力都打不来的我真是太弱了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
//三进制状压 0->没打 1->打了没吃 2->打了吃了 
#include<stdio.h>
#include<iostream>
#include<math.h>
#include<algorithm>
#include<string.h>
#include<vector>
#define ll long long
#define maxn 15
#define maxx 4783970
using namespace std;
int A,D;
ll H;
int N,M,T,K;
int h[maxn],a[maxn],d[maxn],s[maxn];
int ph[maxn],pa[maxn],pd[maxn],pm[maxn];
int mi[maxn];
int fa[maxx],fd[maxx],fm[maxx];
ll f[maxx];
vector<int>Pre[maxn];
void ins(int a,int b){
	Pre[a].push_back(b);
}
ll beat(ll H,int A,int D,int M,int h,int a,int d,int s){
	if(s&8)a=A,d=D;
	if(s&2)D=0;
	int o=1+((s>>2)&1);
	int X=max(0,a-D)*o;//怪伤 
	int x=max(0,A-d);//人伤 
	if(x==0)return 0;
	ll S=1ll*((h-1)/x+1-(~s&1))*X;
	if(S>H+M)return 0;
	if(S>M)H=H-(S-M);
	return H;
}
int main(){
	mi[0]=1;
	for(int i=1;i<15;++i)mi[i]=mi[i-1]+(mi[i-1]<<1);
	scanf("%d",&T);
	while(T--){
		scanf("%lld%d%d%d",&H,&A,&D,&M);
		scanf("%d",&N);
		//
		for(int i=1;i<=N;++i)Pre[i].clear();
		memset(f,0,sizeof(f));
		f[0]=H;
		//
		for(int i=1;i<=N;++i){
			scanf("%d%d%d%d",&h[i],&a[i],&d[i],&s[i]);
			scanf("%d%d%d%d",&pa[i],&pd[i],&pm[i],&ph[i]);
		}
		scanf("%d",&K);
		int u,v;
		for(int i=1;i<=K;++i){
			scanf("%d%d",&u,&v);
			ins(v,u);//***
		}
		int tot=mi[N]-1;
		for(int k=0;k<=tot;++k){
			fa[k]=A,fd[k]=D,fm[k]=M;
			for(int i=1;i<=N;++i){
				if(k/mi[i-1]%3==2){
					fa[k]+=pa[i],fd[k]+=pd[i],fm[k]+=pm[i];
				}
			}
		}
		for(int k=0;k<=tot;++k){
			if(!f[k])continue;
			for(int i=1;i<=N;++i){
				if(k/mi[i-1]%3==0){
					bool bz=0;
					for(int j=0;j<Pre[i].size();++j){
						if(k/mi[Pre[i][j]-1]%3==0){
							bz=1;
							break;
						}
					}
					if(bz)continue;
					ll S=beat(f[k],fa[k],fd[k],fm[k],h[i],a[i],d[i],s[i]);
					if(S>0)f[k+mi[i-1]]=max(f[k+mi[i-1]],S);
				}
				else{
					if(k/mi[i-1]%3==1){
						f[k+mi[i-1]]=max(f[k+mi[i-1]],f[k]+ph[i]);
					}
				}
			}
		}
		if(f[tot]==0)printf("-1\n");
		else printf("%lld\n",f[tot]);
	}
	return 0;
}
0%
``` ```