博弈DP：PIPI的炸弹

落日映苍穹つ 2023-10-06 20:49 2阅读 0赞

## 博弈DP：PIPI的炸弹 ##

#### 文章目录 ####

*  博弈DP：PIPI的炸弹
 *   *   *  问题
         *  思路
         *  代码

#### 问题 ####

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 1]

#### 思路 ####

本题是一道博弈类的动态规划问题，一般而言这类问题为如下形式：博弈为两方游戏，一方按照规则先行动，行动完后把当前局面交给对方，对方再按照规则继续行动，行动完后把局面又重新交回来。以此类推，双方轮流行动，直到满足一定条件，则某方胜或者负。  
  这类问题关键在于先手的转换，比如对于当前先手的人来说，他进行操作后，把某个局面交给对方。那么对方就以先手的情况来面对一个新的局面。因此DP数组需要去保存某个局面下会导致当前先手胜还是先手负。  
  以本题为例，我们设状态DP\[i\]，DP\[i\]为1表示倒计时为i时，此时的先手必胜，为0则此时的先手必负。显然DP\[0\]为0，当倒计时为0时，先手被炸死，先手必负。当`i>0 && i<=a`，双方无法调快时间（因为调快时间自己会被炸死），只能花费1s把炸弹给别人，则DP\[i\]=DP\[i-1\]^1，这里解释一下：

> ^表示异或运算，若DP\[i - 1\] = 1，倒计时为i - 1时先手胜，则倒计时为i时一定是先手负，即DP\[i\] = 0，因为下一个局面的先手是上一个局面的后手。比如倒计时为3时，先手A必胜，则我们可以反推出倒计时为4时，B花1s把炸弹给A，先手B必负

当`i>a && i<=b+1`，先手总能调快到只剩1s，然后花1s给对方炸死对方，则DP\[i\]=1。当`i > b+1`时，这时先手可以选择调快也可以选择不调快，选择不调快，下一个局面就是DP\[i - 1\]，选择调快，下一个局面是`DP[i-j-1](j >= a && j <= b)`，只要DP\[i - 1\]和DP\[i-j-1\]中有一个为0，则当前先手必胜，DP\[i\] = 1，否则不管当前先手怎么玩出花来，他都必负，DP\[i\] = 0。  
  最后只要判断DP\[x\]即可得出答案。  
  上述状态转移过程中，当前局面先手是胜还是负，取决于操作之后的局面先手的胜负，初始时我们即使只知道DP数组的一个元素值DP\[0\] = 0，也能经过重重反演，像因果律中的由果索因一样计算出所有局面的胜负。

#### 代码 ####

import java.util.*;
    
    public class Main {
        
        // 1表示先手胜,0表示先手负
        static int[] dp = new int[1000005];
        public static void main(String[] args) {
        
            int x, a, b, i, j;
            Scanner scanner = new Scanner(System.in);
            x = scanner.nextInt();
            a = scanner.nextInt();
            b = scanner.nextInt();
            dp[0] = 0;
            for (i = 1; i <= x; i++) {
        
                if (i <= a) {
        
                    dp[i] = dp[i - 1] ^ 1;
                } else if (i <= b + 1) {
        
                    dp[i] = 1;
                } else {
        
                    dp[i] = 0;
                    if (dp[i - 1] == 0) {
        
                        dp[i] = 1;
                    } else {
        
                        for (j = a; j <= b; j++) {
        
                            if (dp[i - j - 1] == 0) {
        
                                dp[i] = 1;
                                break;
                            }
                        }
                    }
                }
            }
            System.out.println(dp[x] == 1 ? "PIPI" : "POPO");
        }
    }

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/57db029a304b49ecb6a496e299a1cd5a.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/d21b38b7e74d4956a1a824f634964f6e.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16