Acwing.1388 游戏(区间DP&对抗思想)

题目

玩家一和玩家二共同玩一个小游戏。

给定一个包含 N个正整数的序列。

由玩家一开始,双方交替行动。

每次行动可以在数列的两端之中任选一个数字将其取走,并给自己增加相应数字的分数。(双初始分都是 0分)

当所有数字都被取完时,游戏结束。

分更高的一方获胜。

请计算,如果双方都采取最优策略进行游戏,则游戏结束时,双方的得分各是多少。

输入格式

第一行包含整数 N。

后面若干行包含 N个整数,表示这个序列。注意每行不一定恰好包含一个数。

输出格式

共一行,两个整数,分别表示玩家一和玩家二的最终得分。

数据范围

2≤N≤100

数列中的数字的取值范围为 [1,200]

  • 输入样例:
6
4 7 2 9
5 2
  • 输出样例:
18 11

题解

import java.util.Scanner;

/**
 * @author akuya
 * @create 2024-04-03-18:47
 */
public class Main {
    static int N=105;
    static int n;
    static int w[]=new int[N];
    static int f[][]=new int[N][N];
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        n=scanner.nextInt();
        for(int i=0;i<n;i++){
            w[i]=scanner.nextInt();
        }

        for(int len=1;len<=n;len++){
            for(int i=0;i+len-1<n;i++){
                int j=i+len-1;
                if(len==1)//区间长度为1则只有一个可拿。
                    f[i][j]=w[i];
                else
                    f[i][j]=Math.max(w[i]-f[i+1][j],w[j]-f[i][j-1]);
            }
        }


        int sum=0,d=f[0][n-1];
        for(int i=0;i<n;i++) sum+=w[i];

        //A+B=SUM A-B=d
        //A=SUM-D/2
        //B=SUM-D/2

        System.out.println((sum+d)/2+" "+(sum-d)/2);



    }
}

思路

首先这道题用的是区间DP,区间DP与背包问题一样有具体的模板,第一层遍历区间长度,第二层遍历左端点。dp数组的两个元素也利索当然得是区间的两个端点。
这道题是一道经典的对抗问题,要求比较谁更高,也就是使自己的分数与对方的分数的分差更大,因此dp数组为选择i到j区间里分差最大的选择。在每第i-j区域的选择里,我们可以从左或者从右选,在这次选择之前是对方选择,对方肯定会选择对自己更优的方案,也就是使自己方差和我们方差最大的方案,设为a(a=f[i+1][j]orf[i][j-1])。那么在这次选择之前,我们与对方的方差是-a。我们需要在这样的前提情况下选择与对方方差最大的方案,也就是-a+左或者-a加上右。
完成以上逻辑即可解答出本题。

在这里插入图片描述

相关推荐

  1. AcWing802. 区间思路

    2024-04-04 00:02:01       27 阅读
  2. 区间DP,LeetCode 1690. 石子游戏 VII

    2024-04-04 00:02:01       20 阅读
  3. DP+贪心】跳跃游戏

    2024-04-04 00:02:01       11 阅读

最近更新

  1. 冒烟测试(Smoke Testing)简介

    2024-04-04 00:02:01       0 阅读
  2. 题解:P9426 [蓝桥杯 2023 国 B] 抓娃娃

    2024-04-04 00:02:01       0 阅读

热门阅读

  1. 财务管理 基础1:除了利润,一切都是扯淡

    2024-04-04 00:02:01       3 阅读
  2. GDAL源码剖析(十一)之OGR投影说明

    2024-04-04 00:02:01       3 阅读
  3. Go语言介绍及Go语言成功的项目列举

    2024-04-04 00:02:01       3 阅读
  4. 【前端浅谈】前端开发语言有哪些

    2024-04-04 00:02:01       3 阅读
  5. 每日一题 --- 有效的括号[力扣][Go]

    2024-04-04 00:02:01       4 阅读
  6. 集群式无人机仿真环境和数据集

    2024-04-04 00:02:01       5 阅读
  7. LeetCode-热题100:234. 回文链表

    2024-04-04 00:02:01       6 阅读
  8. C++(12): std::mutex及其高级变种的使用

    2024-04-04 00:02:01       4 阅读
  9. YOLO_Tracking 实践 (环境搭建 & 案例测试)

    2024-04-04 00:02:01       4 阅读