业务网站制作,专门制作网页的工具,南宁网站设计多少钱,创建一个网站英语题目
玩家一和玩家二共同玩一个小游戏。
给定一个包含 N个正整数的序列。
由玩家一开始#xff0c;双方交替行动。
每次行动可以在数列的两端之中任选一个数字将其取走#xff0c;并给自己增加相应数字的分数。#xff08;双初始分都是 0分#xff09;
当所有数字都被…题目
玩家一和玩家二共同玩一个小游戏。
给定一个包含 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 N105;static int n;static int w[]new int[N];static int f[][]new int[N][N];public static void main(String[] args) {Scanner scannernew Scanner(System.in);nscanner.nextInt();for(int i0;in;i){w[i]scanner.nextInt();}for(int len1;lenn;len){for(int i0;ilen-1n;i){int jilen-1;if(len1)//区间长度为1则只有一个可拿。f[i][j]w[i];elsef[i][j]Math.max(w[i]-f[i1][j],w[j]-f[i][j-1]);}}int sum0,df[0][n-1];for(int i0;in;i) sumw[i];//ABSUM A-Bd//ASUM-D/2//BSUM-D/2System.out.println((sumd)/2 (sum-d)/2);}
}
思路
首先这道题用的是区间DP区间DP与背包问题一样有具体的模板第一层遍历区间长度第二层遍历左端点。dp数组的两个元素也利索当然得是区间的两个端点。 这道题是一道经典的对抗问题要求比较谁更高也就是使自己的分数与对方的分数的分差更大因此dp数组为选择i到j区间里分差最大的选择。在每第i-j区域的选择里我们可以从左或者从右选在这次选择之前是对方选择对方肯定会选择对自己更优的方案也就是使自己方差和我们方差最大的方案设为aaf[i1][j]orf[i][j-1]。那么在这次选择之前我们与对方的方差是-a。我们需要在这样的前提情况下选择与对方方差最大的方案也就是-a左或者-a加上右。 完成以上逻辑即可解答出本题。
