[比赛][博弈论][SG表] 2018 ICPC徐州网络赛 B BE, GE or NE

赛后过题，心塞。

这题搞明白以后就是一个暴力打SG表的过程，-1表示bad，0表示normal，1表示good，从最后一轮开始，分奇偶轮，如果是奇数轮也就是先手轮，那就尽可能往1，也就是往大了转移，如果是偶数轮，也就是后手轮，那就往小了转移。真的是服了，这么简单当时就是没想到，唉。

因为n只有1000，每次的状态也最多只有200，（妈的限制上下界不就是为了可以暴力打表或者暴搜吗。。这么明显的特征没看出来我也是呵呵）想到这儿的时候直接明白了，为什么比赛时候那么多人过还那么高的通过率，呵呵呵呵呵，当时脑子真是短路。心情复杂。思考。

 

#include 

using namespace std;
typedef long long LL;
const int maxn=1e3+5;

int ops[maxn][4];
int st[maxn][205];
int main()
{
    int n,m,k,l;
    scanf("%d%d%d%d",&n,&m,&k,&l);
    k+=100;l+=100;m+=100;
    for (int i=1;i<=n;i++)
        scanf("%d%d%d",&ops[i][1],&ops[i][2],&ops[i][3]);
    for (int i=0;i<=200;i++)
    {
        if(i<=l)
            st[n+1][i]=-1;
        else if(i>=k)
            st[n+1][i]=1;
        else
            st[n+1][i]=0;
    }
    for (int i=n;i>0;i--)
    {
        for (int j=0;j<=200;j++)
        {
            int a=-1,b=1;
            if(ops[i][1])
            {
                a=max(a,st[i+1][min(200,j+ops[i][1])]);
                b=min(b,st[i+1][min(200,j+ops[i][1])]);
            }
            if(ops[i][2])
            {
                a=max(a,st[i+1][max(0,j-ops[i][2])]);
                b=min(b,st[i+1][max(0,j-ops[i][2])]);
            }
            if(ops[i][3])
            {
                a=max(a,st[i+1][200-j]);
                b=min(b,st[i+1][200-j]);
            }
            if(i%2)//error
                st[i][j]=a;
            else
                st[i][j]=b;
        }
    }
    if(st[1][m]==1)
        cout<<"Good Ending\n";
    else if(st[1][m]==-1)
        cout<<"Bad Ending\n";
    else
        cout<<"Normal Ending\n";
    return 0;
}