P11642 【MX-X8-T1】「TAOI-3」幸运草题解

lihaoda · 2025-02-01 10:55:14 · 题解

审题

题意：可以从 a_1 , a_2 , ... a_n 中选择一个区间，将该区间中的数全部修改成 x，求a_1 至 a_n最大的总和。

解题

1. 完全暴力

从 1 至 n 中选取一个数作为 l，再从 l 至 n 中选择一个数作为 r，将 l 至 r 修改为 x，再 O(n) 求区间和，整体复杂度 O(n^{3})。勉强能过 n \le 500。

// 不会真有人看这个代码吧……
#include<bits/stdc++.h>
#define int long long

using namespace std;

int read() {
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9') {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9')
        x=x*10+ch-48,ch=getchar();
    return x*f;
}
void write(int x) {
    if(x<0) x=-x,putchar('-');
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

int a[100007];
int ans;

signed main(){
    int n,x;
    cin >> n >> x;
    for(int i=1;i<=n;++i) cin >> a[i];
    for(int i=1;i<=n;++i){
        for(int j=i;j<=n;++j){
            int sum=0;
            for(int k=1;k<=n;++k){
                if(k>=i&&k<=j){
                    sum+=x;
                }else{
                    sum+=a[k];
                }
            }
//          cout << i << ' ' << j << ':' << sum << '\n';
            ans = max(ans,sum);
        }
    }
    cout << ans;
}

2.前缀和优化

前缀和可以让求区间和变成 O(1)，这样总体时间复杂度能变成 O(n^{2})，能过 n \le 3 \times 10^{3}。

#include<bits/stdc++.h>
#define int long long

using namespace std;

int read() {
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9') {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9')
        x=x*10+ch-48,ch=getchar();
    return x*f;
}
void write(int x) {
    if(x<0) x=-x,putchar('-');
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

int a[100007];
int sum[100007];
int ans;

signed main(){
    int n,x;
    cin >> n >> x;
    for(int i=1;i<=n;++i) cin >> a[i],sum[i]=sum[i-1]+a[i];
    for(int i=1;i<=n;++i){
        for(int j=i;j<=n;++j){
            ans = max(sum[i-1]+(j-i+1)*x+sum[n]-sum[j],ans);
        }
    }
    cout << ans;
}

3.换位思考

求答案，还有另外一种方法：设 b_i 为 x - a_i，则答案变成了求 b 数组的最大子段和加上 a 数组的和。
求最大子段和，我们就可以参考P4513 小白逛公园，建议可以先做一下这道题。

3.1 dp

使用dp求最大子段和是一个比较明智的选择。不仅拥有O(n)的优秀复杂度，在本题里还能达到惊人的O(1)空间复杂度。具体方法不在这里赘述了。

#include<bits/stdc++.h>
#define int long long
using namespace std;

int dp;
int sum;
int ans;
int n;
int x;

signed main(){
    cin >> n >> x;
    for(int i=1;i<=n;++i){
        int y;
        cin >> y;
        sum += y;
        dp = max(dp+x-y,x-y);
        ans = max(ans,dp);
    }
    cout << sum+ans;//ans一开始为0所以不用特判最大子段和小于0的情况
}

3.2 线段树

除了使用dp算法，我们还可以用线段树和其他数据结构来解题。
我们要求最大子段和，可以用左儿子的最大子段和、右儿子的最大子段和和左儿子的最大后缀和（或右边的最大和）加上右儿子的最大前缀和中的最大值。
而最大后缀和是左儿子的最大后缀和加上右儿子的总和和右儿子的最大后缀和中的最大值。
同理，最大前缀和是右儿子的最大前缀和加上左儿子的总和和左儿子的最大前缀和中的最大值。
建树：

void build(int k,int left,int right){
    tree[k].l = left;
    tree[k].r = right;
    if(left==right){
        tree[k].all_maxsum = a[left];
        tree[k].all_sum = a[left];
        tree[k].left_maxsum = a[left];
        tree[k].right_maxsum = a[left];
        return;
    }
    int mid = (left+right)/2;
    build(2*k,left,mid);
    build(2*k+1,mid+1,right);
    push_up(k);
}

子更新父：

void push_up(int k){
    tree[k].all_sum = tree[2*k].all_sum + tree[2*k+1].all_sum;
    tree[k].left_maxsum = max( tree[2*k].left_maxsum , tree[2*k].all_sum + tree[2*k+1].left_maxsum );
    tree[k].right_maxsum = max( tree[2*k+1].right_maxsum , tree[2*k+1].all_sum + tree[2*k].right_maxsum );
    tree[k].all_maxsum = max( max( tree[2*k].all_maxsum , tree[2*k+1].all_maxsum ) , tree[2*k].right_maxsum + tree[2*k+1].left_maxsum );
}

最后返回max(tree[1].all_maxsum+sum,sum)的最大值就行了。

代码

#include<bits/stdc++.h>
#define N 100000+7
#define int long long
//typedef ll long long

using namespace std;

int n,x;
int a[N];
int sum;
struct SegTree{ // SegmentTree
    int l;
    int r;
    int all_sum;//总和
    int left_maxsum;//最大前缀和
    int right_maxsum;//最大后缀和
    int all_maxsum; //最大子段和
}tree[8*N];

void push_up(int k){
    tree[k].all_sum = tree[2*k].all_sum + tree[2*k+1].all_sum;
    tree[k].left_maxsum = max( tree[2*k].left_maxsum , tree[2*k].all_sum + tree[2*k+1].left_maxsum );
    tree[k].right_maxsum = max( tree[2*k+1].right_maxsum , tree[2*k+1].all_sum + tree[2*k].right_maxsum );
    tree[k].all_maxsum = max( max( tree[2*k].all_maxsum , tree[2*k+1].all_maxsum ) , tree[2*k].right_maxsum + tree[2*k+1].left_maxsum );
}

void build(int k,int left,int right){
    tree[k].l = left;
    tree[k].r = right;
    if(left==right){
        tree[k].all_maxsum = a[left];
        tree[k].all_sum = a[left];
        tree[k].left_maxsum = a[left];
        tree[k].right_maxsum = a[left];
        return;
    }
    int mid = (left+right)/2;
    build(2*k,left,mid);
    build(2*k+1,mid+1,right);
    push_up(k);
}
signed main(){
    cin >> n >> x;
    for(int i=1;i<=n;++i){
    int y;
        cin >> y;
        sum+=y;
        a[i] = x-y;
    }
    build(1,1,n);
    cout << max(tree[1].all_maxsum+sum,sum);//注意可能最大子段和是负的
}

P11642 【MX-X8-T1】「TAOI-3」幸运草 题解

审题

解题