2018ICPC徐州区域赛网络赛B（逆序枚举或者正序深度搜索）

#include<bits/stdc++.h>
using namespace std;
int n,m,k,l;
int x[1007],y[1007],z[1007];
int dp[1007][207];
void init()//预处理n次处理后的情况
{
    for(int i=0;i<=l+100;i++)
        dp[n+1][i]=-1;
    for(int i=l+101;i<k+100;i++)
        dp[n+1][i]=0;
    for(int i=k+100;i<=200;i++)
        dp[n+1][i]=1;
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&k,&l);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&x[i],&y[i],&z[i]);
    }
    init();
    int a,b,c;
    for(int i=n;i>=1;i--)//已知n次处理后的情况，向前递推
    {
        for(int j=0;j<=200;j++)//枚举每一个分数
        {
            a=-1,b=-1,c=-1;
            if(x[i])
            {
                if(j+x[i]>200)
                    a=200;
                else
                    a=j+x[i];
            }
            if(y[i])
            {
                if(j-y[i]<0)
                    b=0;
                else
                    b=j-y[i];
            }
            if(z[i])
            {
                c=200-j;
            }
            if(i&1)
            {
                if(((a>=0)&&(dp[i+1][a]==1))||((b>=0)&&(dp[i+1][b]==1))||((c>=0)&&(dp[i+1][c]==1)))//任何一种情况可以到达后一种胜利的情况都可以
                {
                    dp[i][j]=1;
                    continue;
                }
                if(((a==-1)||(dp[i+1][a]==-1))&&((b==-1)||(dp[i+1][b]==-1))&&((c==-1)||(dp[i+1][c]==-1)))//别无其他选择只能走入失败的局面
                {
                    dp[i][j]=-1;
                    continue;
                }
                dp[i][j]=0;//虽然赢不了但也输不了
            }
            else//另一个人的视角
            {
                if(((a>=0)&&(dp[i+1][a]==-1))||((b>=0)&&(dp[i+1][b]==-1))||((c>=0)&&(dp[i+1][c]==-1)))
                {
                    dp[i][j]=-1;
                    continue;
                }
                if(((a==-1)||(dp[i+1][a]==1))&&((b==-1)||(dp[i+1][b]==1))&&((c==-1)||(dp[i+1][c]==1)))
                {
                    dp[i][j]=1;
                    continue;
                }
                dp[i][j]=0;
            }
        }
    }
    //相当于已经计算好了以后的每一步，类比象棋
    if(dp[1][m+100]==1)
        printf("Good Ending");
    else if(dp[1][m+100]==0)
        printf("Normal Ending");
    else
        printf("Bad Ending");
    return 0;
}
//当时想了很久，错误在于正向推进使得最后情况过多，实际上正难则反，也可以深度搜索模拟类似的情况，即从第一步开始去寻找一定会赢或者输的情况

巴特西

2018ICPC徐州区域赛网络赛B（逆序枚举或者正序深度搜索）

最新文章

热门文章