2018 ICPC 徐州赛站网络赛 B.BE,GE or NE 博弈论+记忆化搜索
博弈论 记忆化搜索   发布于 2019-08-29   515人围观  0条评论
博弈论 记忆化搜索   发表于 2019-08-29   515人围观  0条评论

Description

In a world where ordinary people cannot reach, a boy named "Koutarou" and a girl named "Sena" are playing a video game. The game system of this video game is quite unique: in the process of playing this game, you need to constantly face the choice, each time you choose the game will provide 1−3 options, the player can only choose one of them. Each option has an effect on a "score" parameter in the game. Some options will increase the score, some options will reduce the score, and some options will change the score to a value multiplied by −1 .

That is, if there are three options in a selection, the score will be increased by 1, decreased by 1, or multiplied by −1. The score before the selection is 888. Then selecting option 1 will make the score become 9, and selecting option 2 will make the score 7 and select option 3 to make the score −8. Note that the score has an upper limit of 100 and a lower limit of −100. If the score is 99 at this time, an option that makes the score +2 is selected. After that, the score will change to 100 and vice versa .

After all the choices have been made, the score will affect the ending of the game. If the score is greater than or equal to a certain value k, it will enter a good ending; if it is less than or equal to a certain value l, it will enter the bad ending; if both conditions are not satisfied, it will enter the normal ending. Now, Koutarou and Sena want to play the good endings and the bad endings respectively. They refused to give up each other and finally decided to use the "one person to make a choice" way to play the game, Koutarou first choose. Now assume that they all know the initial score, the impact of each option, and the k, l values, and decide to choose in the way that works best for them. (That is, they will try their best to play the ending they want. If it's impossible, they would rather normal ending than the ending their rival wants.)

Koutarou and Sena are playing very happy, but I believe you have seen through the final ending. Now give you the initial score, the kkk value, the lll value, and the effect of each option on the score. Can you answer the final ending of the game?

Input

The first line contains four integers n,m,k,l1≤n≤1000 −100≤m≤100 , −100≤l<k≤100), represents the number of choices, the initial score, the minimum score required to enter a good ending, and the highest score required to enter a bad ending, respectively.

Each of the next nnn lines contains three integers a,b,ca,b,ca,b,ca≥0 , b≥0 ,c=0 or c=1),indicates the options that appear in this selection,in which a=0 means there is no option to increase the score in this selection, a>0 means there is an option in this selection to increase the score by a ; b=0 means there is no option to decrease the score in this selection, b>0 means there is an option in this selection to decrease the score by b; c=0means there is no option to multiply the score by −1 in this selection , c=1 means there is exactly an option in this selection to multiply the score by −1. It is guaranteed that a,b,c are not equal to 0 at the same time.

Output

One line contains the final ending of the game. If it will enter a good ending,print "Good Ending"(without quotes); if it will enter a bad ending,print "Bad Ending"(without quotes);otherwise print "Normal Ending"(without quotes)

题目大意

两个人的博弈,一开始有一个初始分数值,有三种操作,分别为+a,-b和变为相反数,先手希望走向Good Ending,后手希望走向Bad Ending,如果不能的话都希望走向Normal Ending。两人都以最优策略进行游戏。

求问n轮过后结局是哪一种。

题解

博弈论的经典题目(算是吧,做法挺经典的)

首先我们知道对于某一个状态,其必胜态条件是子状态中至少有一个其必败态,其必败态条件是子状态中全为必胜态。

对于这种最朴素的问题,我们就采用对对应状态的记忆化搜索来解决,这是一种经典解法。

对于此题来讲,我们的状态就是当前为第几回合和当前分数的组合。

我们定义先手胜利为0,后手胜利为2,平局为1.

那么对于先手,肯定是取后面的状态中返回值最小的,而对于后手,肯定是取后面的状态中返回值最大的,因为能有利于自己的话,采取最优策略一定不会选择去往平局上靠。

用一个二维数组记忆化一下就可以了。

代码

#include <bits/stdc++.h>
using namespace std;
map<int,int>id;
const int maxn = 1e3+5;
int dp[maxn][225];
int a[maxn],b[maxn],c[maxn];
int n,m,k,l;
int dfs(int now,int score){
    if(now == n+1){
        if(score >= k)return 0;
        else if(score <= l)return 2;
        else return 1;
    }
    int ans;
    if(dp[now][id[score]] != -1)return dp[now][id[score]];
    if(now & 1){
        ans = 2;
        if(a[now])ans = min(ans,dfs(now+1,min(100,score + a[now])));
        if(b[now])ans = min(ans,dfs(now+1,max(-100,score - b[now])));
        if(c[now])ans = min(ans,dfs(now+1,-score));
    }
    else{
        ans = 0;
        if(a[now])ans = max(ans,dfs(now+1,min(100,score + a[now])));
        if(b[now])ans = max(ans,dfs(now+1,max(-100,score - b[now])));
        if(c[now])ans = max(ans,dfs(now+1,-score));
    }
    return dp[now][id[score]] = ans;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin >> n >> m >> k >> l;
    memset(dp,-1,sizeof(dp));
    for(int i = 0;i <= 200;++i){
        id[i - 100] = i;
    }
    for(int i = 1;i <= n;++i){
        cin >> a[i] >> b[i] >> c[i];
    }
    int ans = dfs(1,m);
    if(ans == 0){
        cout << "Good Ending" << endl;
    }
    else if(ans == 1)cout << "Normal Ending" << endl;
    else cout << "Bad Ending" << endl;
    return 0;
}


上一篇: 2019 南京网络赛 A.The beautiful values of the palace 思维题+扫描线+树状数组

下一篇: 2018 ICPC 徐州赛站网络赛 H Ryuji doesn't want to study 线段树

立即登录,发表评论
没有帐号?立即注册
0 条评论