2018ICPC-徐州网络赛

链接:2018ICPC-徐州网络赛

题解

  • 据说博弈也可以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

    #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #define rep(i,x,y) for(register int i=x;i<=y;++i)
    #define repd(i,x,y) for(register int i=x;i>=y;--i)
    #define ll long long
    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;
    }