题解
- 据说博弈也可以A,赛场上题读错了。。。
- 其实很简单,A会尽量使答案变大,B会尽量使答案变小。这样就是一个简单的DP。
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
using namespace std;
const int N=1e3+7;
const int st=101;
template<typename T>inline void read(T &x){
char c;int sign=1;x=0;
do{c=getchar();if(c=='-')sign=-1;}while(c<'0'||c>'9');
do{x=x*10+c-'0';c=getchar();}while(c>='0'&&c<='9');
x*=sign;
}
int dp[2][300],op[N][3],n,m,k,l;
int main(){
read(n);read(m);read(k);read(l);
int cur=0;
rep(i,1,n)rep(j,0,2)read(op[i][j]);
rep(i,-100,100)dp[cur][i+st]=i;
repd(i,n,1){
cur^=1;
if(i&1)rep(j,-100,100){
dp[cur][j+st]=-100;
int k;
if(op[i][0]){
k=min(100,j+op[i][0]);
dp[cur][j+st]=max(dp[cur][j+st],dp[cur^1][k+st]);
}
if(op[i][1]){
k=max(-100,j-op[i][1]);
dp[cur][j+st]=max(dp[cur][j+st],dp[cur^1][k+st]);
}
if(op[i][2]){
k=-j;
dp[cur][j+st]=max(dp[cur][j+st],dp[cur^1][k+st]);
}
}
else rep(j,-100,100){
dp[cur][j+st]=100;
int k;
if(op[i][0]){
k=min(100,j+op[i][0]);
dp[cur][j+st]=min(dp[cur][j+st],dp[cur^1][k+st]);
}
if(op[i][1]){
k=max(-100,j-op[i][1]);
dp[cur][j+st]=min(dp[cur][j+st],dp[cur^1][k+st]);
}
if(op[i][2]){
k=-j;
dp[cur][j+st]=min(dp[cur][j+st],dp[cur^1][k+st]);
}
}
}
if(dp[cur][m+st]>=k)puts("Good Ending");
else if(dp[cur][m+st]>l)puts("Normal Ending");
else puts("Bad Ending");
return 0;
}