#P1899. 第3题-玩游戏
-
1000ms
Tried: 114
Accepted: 3
Difficulty: 8
所属公司 :
美团
时间 :2024年8月17日
第3题-玩游戏
思路:动态规划
以下思路考场能AC,但是有点问题。
定义dp[i][j][0]代表a[i,...,j]中连续子段的最小值
定义dp[i][j][1]代表a[i,...,j]中连续子段的最大值
可以采用二维循环求出dp数组。
之后枚举小乖选择哪个子段,然后计算这个子段情况下小坏所能达到的最小贡献,并取最大值即为最终答案。
注意博弈思想,二者均是选择最优的方案,并且是小乖先手。当小乖操作完毕后,无论是什么结果,小坏的最优操作方案均为:
- k>0,选取最小的连续子段和,并将该子段乘k
- k<0,选取最大的连续子段和,并将该子段乘k
而对于小乖来说,如果在小坏操作完后,其不能达到理想的最大值,那么小乖就应当选择另外一种操作,以达到理想的最大值。
代码
java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int length, multiplier;
length = scanner.nextInt();
multiplier = scanner.nextInt();
long[] elements = new long[length + 1];
long[] prefixSum = new long[length + 1];
long[][][] dp = new long[length + 1][length + 1][2];
for (int i = 1; i <= length; i++) {
elements[i] = scanner.nextLong();
prefixSum[i] = prefixSum[i - 1] + elements[i];
}
for (int segment = 1; segment <= length; segment++) {
for (int start = 1; start + segment - 1 <= length; start++) {
int end = start + segment - 1;
if (segment == 1) {
dp[start][end][0] = dp[start][end][1] = elements[start];
} else {
dp[start][end][0] = Math.min(Math.min(dp[start + 1][end][0], dp[start][end - 1][0]), calculateSum(prefixSum, start, end));
dp[start][end][1] = Math.max(Math.max(dp[start + 1][end][1], dp[start][end - 1][1]), calculateSum(prefixSum, start, end));
}
}
}
long maximumValue = Long.MIN_VALUE;
for (int i = 1; i <= length; i++) {
for (int j = i; j <= length; j++) {
long product1 = calculateSum(prefixSum, i, j) * (multiplier - 1);
long product2 = Math.min(dp[i][j][0] * multiplier * (multiplier - 1), dp[i][j][1] * multiplier * (multiplier - 1));
if (i != 1) {
product2 = Math.min(product2, Math.min(dp[1][i - 1][0] * (multiplier - 1), dp[1][i - 1][1] * (multiplier - 1)));
}
if (j != length) {
product2 = Math.min(product2, Math.min(dp[j + 1][length][0] * (multiplier - 1), dp[j + 1][length][1] * (multiplier - 1)));
}
maximumValue = Math.max(maximumValue, product1 + product2);
}
}
System.out.println(calculateSum(prefixSum, 1, length) + maximumValue);
}
private static long calculateSum(long[] prefixSum, int left, int right) {
return prefixSum[right] - prefixSum[left - 1];
}
}
思路:线段树维护
比较暴力易想的方法,用线段树维护区间最大最小值。
暴力枚举小乖的操作区间[l,r],然后在线段树上修改并维护。
之后,如果k>0,那么小坏需要找到最小子段和,如果k<0,那么小坏需要找到最大字段和。而这两个和都维护在线段树的根部了,可以直接获得。
当k=0时,答案为0。因为如果最后和大于0,小坏会选所有数字乘0;而如果最后和小于0,那么小乖会选所有数字乘0。
时间复杂度为O(N2logN)
C++
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lson (num<<1)
#define rson (num<<1|1)
const int maxn=1e3+10;
int n;
ll k;
ll a[maxn];
struct node{
ll lmin,rmin,lmax,rmax,mx,mi,sum;
} tree[maxn<<2];
void build(int l,int r,int num){
if(l==r){
tree[num]= (node){a[l],a[l],a[l],a[l],a[l],a[l],a[l]};
return;
}
int mid=(l+r)>>1;
build(l,mid,lson);
build(mid+1,r,rson);
tree[num].sum = tree[lson].sum+tree[rson].sum;
tree[num].mx = max({tree[lson].mx, tree[rson].mx, tree[lson].rmax+tree[rson].lmax});
tree[num].mi = min({tree[lson].mi, tree[rson].mi, tree[lson].rmin+tree[rson].lmin});
tree[num].lmax = max({tree[lson].lmax, tree[lson].sum+tree[rson].lmax});
tree[num].lmin = min({tree[lson].lmin, tree[lson].sum+tree[rson].lmin});
tree[num].rmax = max({tree[rson].rmax, tree[rson].sum+tree[lson].rmax});
tree[num].rmin = min({tree[rson].lmin, tree[rson].sum+tree[lson].rmin});
}
void modify(int st,int ed,int l,int r,int num,ll val,bool flag){
if(st<=l&&ed>=r){
if(flag){
tree[num].sum*=k;
if(k>0){
tree[num].mx*=k;
tree[num].mi*=k;
tree[num].lmax*=k;
tree[num].lmin*=k;
tree[num].rmax*=k;
tree[num].rmin*=k;
}else{
ll mi=tree[num].mi, mx=tree[num].mx;
tree[num].mx=mi*k;
tree[num].mi=mx*k;
ll lmax=tree[num].lmax, lmin=tree[num].lmin;
tree[num].lmax=lmin*k;
tree[num].lmin=lmax*k;
ll rmax=tree[num].rmax, rmin=tree[num].rmin;
tree[num].rmax=rmin*k;
tree[num].rmin=rmax*k;
}
}else{
tree[num].sum/=k;
if(k>0){
tree[num].mx/=k;
tree[num].mi/=k;
tree[num].lmax/=k;
tree[num].lmin/=k;
tree[num].rmax/=k;
tree[num].rmin/=k;
}else{
ll mi=tree[num].mi, mx=tree[num].mx;
tree[num].mx=mi/k;
tree[num].mi=mx/k;
ll lmax=tree[num].lmax, lmin=tree[num].lmin;
tree[num].lmax=lmin/k;
tree[num].lmin=lmax/k;
ll rmax=tree[num].rmax, rmin=tree[num].rmin;
tree[num].rmax=rmin/k;
tree[num].rmin=rmax/k;
}
}
return;
}
int mid=(l+r)>>1;
if(mid>=st){
modify(st,ed,l,mid,lson,val,flag);
}
if(mid<ed){
modify(st,ed,mid+1,r,rson,val,flag);
}
tree[num].sum = tree[lson].sum+tree[rson].sum;
tree[num].mx = max({tree[lson].mx, tree[rson].mx, tree[lson].rmax+tree[rson].lmax});
tree[num].mi = min({tree[lson].mi, tree[rson].mi, tree[lson].rmin+tree[rson].lmin});
tree[num].lmax = max({tree[lson].lmax, tree[lson].sum+tree[rson].lmax});
tree[num].lmin = min({tree[lson].lmin, tree[lson].sum+tree[rson].lmin});
tree[num].rmax = max({tree[rson].rmax, tree[rson].sum+tree[lson].rmax});
tree[num].rmin = min({tree[rson].rmin, tree[rson].sum+tree[lson].rmin});
}
int main(){
std::ios::sync_with_stdio(false);
cin>>n>>k;
for(int i=1;i<=n;++i){
cin>>a[i];
}
if(k==0){
cout<<0;
return 0;
}
build(1,n,1);
ll ans=LLONG_MIN;
if(k>0){
for(int len=1;len<=n;++len){
for(int i=1;i+len-1<=n;++i){
int j=i+len-1;
if(i==9&&j==17){
bool flag=true;
}
modify(i,j,1,n,1,k,1);
ans=max(ans, tree[1].sum + tree[1].mi*(k-1));
modify(i,j,1,n,1,k,0);
}
}
}else{
for(int len=1;len<=n;++len){
for(int i=1;i+len-1<=n;++i){
int j=i+len-1;
modify(i,j,1,n,1,k,1);
ans=max(ans, tree[1].sum + tree[1].mx*(k-1));
modify(i,j,1,n,1,k,0);
}
}
}
cout<<ans;
return 0;
}
小乖和小坏在玩一个游戏,游戏中有一个长度为 n 的数组a1,a2,...,an 和一个固定的整数k。游戏规则如下,双方都会执行最优策略:
第一步,小乖选择一个非空的区间 [l,r],将这个区间中的所有数字都乘上 k。
第二步, 小坏选择一个非空的区间 [l,r], 将这个区间中的所有数字都乘上 k。
记sum=i=1∑nai 小坏想让sum尽可能小,小乖想让sum尽可能大,你需要求出最后 sum 的值。
输入描述
第一行输入两个整数 n 和 k$(10^{-5} ≤ k ≤ 10^5, 1 ≤ n ≤ 1000; -10^5 ≤ a_i ≤ 10^5)$,代表数组长度和固定的整数。
第二行输入 n 个整数 a1,a2,...,an, (−105≤ai≤105)代表数组。
输出描述
在一行上输出一个整数表示答案。
示例 1
输入
6 2
-1 -2 -3 1 2 3
输出
0
说明
小乖会选择区间[4,6],数组变成{−1,−2,−3,2,4,6};
小坏会选择区间[1,3],数组变成{−2,−4,−6,2,4,6};
数组总和为 0。