ACM-ICPC 2018 徐州赛区网络预赛-B.BE, GE or NE-对抗博弈dp

题意：

有两个神仙玩游戏，A想让最后得分大于等于K，B想让最后得分小于等于L，每次有1~3种选择，可使当前分+x，当前分-x，当前分*-1
三种选择至少存在一种，注意游戏中的分数有上下界限制，-100~100 若超过则按边界算，因为A和B都是神仙，所以他们每次都做最优选择，问最后游戏的结果

思路：

对抗博弈中的常用算法MiniMax，此算法的思路很简单，可自行百度理解
在本题中，若从上向下进行MiniMax搜索，一定会超时(O(3^n))，所以考虑从底向上，枚举-100~100的所有情况
dp[i][j]表示第i次选择时，当前分数为j时能取得的最大/最小值，若A选则取最大值，B选则取最小值
注意分数的边界限制，需要在转移时处理，详见代码

对应三种选择，有三种状态转移:
a. dp[i][j]=max/min(dp[i][j],dp[i+1][j+a[i]])
b. dp[i][j]=max/min(dp[i][j],dp[i+1][j+b[i]])
c. dp[i][j]=max/min(dp[i][j],dp[i+1][-j])

代码：

#include <iostream>
using namespace std;

const int tp=100;      //偏移量，将-100~100映射到0~200
struct node
{
    int x,y,z;
}a[1005];
int dp[1005][205];    //dp[i][j]表示第i次选择，当前值为j时，能得到的最大/最小值
int main()
{
    int n,m,k,l;
    cin>>n>>m>>k>>l;
    for(int i=1;i<=n;i++)
        cin>>a[i].x>>a[i].y>>a[i].z;
    for(int i=-100;i<=100;i++)
        dp[n+1][i+tp]=i;             //初始化最终状态，即搜索树的叶子结点，枚举所有可行情况
    for(int i=n;i>=1;i--)
    {
        for(int j=-100;j<=100;j++)
        {
            int o1=dp[i+1][min(j+a[i].x,100)+tp];     //执行加操作，并将大于100的数处理成100
            int o2=dp[i+1][max(j-a[i].y,-100)+tp];    //执行减操作，并将小于-100的数处理成-100
            int o3=dp[i+1][-j+tp];                    //执行*-1操作
            if(i&1)                                   //当前层为奇数，第一个人操作，选取三种操作后的最大值
            {
                dp[i][j+tp]=-100;                     //边界处理，同上
                if(a[i].x) dp[i][j+tp]=max(dp[i][j+tp],o1);
                if(a[i].y) dp[i][j+tp]=max(dp[i][j+tp],o2);
                if(a[i].z) dp[i][j+tp]=max(dp[i][j+tp],o3);
            }
            else                                     //当前层数为偶数，第二个人操作，选取三种操作后的最小值
            {
                dp[i][j+tp]=100;                     //边界处理，同上
                if(a[i].x) dp[i][j+tp]=min(dp[i][j+tp],o1);
                if(a[i].y) dp[i][j+tp]=min(dp[i][j+tp],o2);
                if(a[i].z) dp[i][j+tp]=min(dp[i][j+tp],o3);
            }
        }
    }
    if(dp[1][m+tp]>=k) cout<<"Good Ending"<<endl;
    else if(dp[1][m+tp]<=l) cout<<"Bad Ending"<<endl;
    else cout<<"Normal Ending"<<endl;
    return 0;
}