链接：https://ac.nowcoder.com/acm/contest/884/C
来源：牛客网
 

时间限制：C/C++ 3秒，其他语言6秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld

题目描述

Your are given two sequences a1…na_{1 \dots n}a1…n​ and b1…nb_{1 \dots n}b1…n​ .You need to answer max⁡1≤l≤r≤n{min(al…r)×sum(bl…r)}\displaystyle \max_{1 \le l \le r \le n} \{min(a_{l \dots r}) \times sum(b_{l \dots r})\}1≤l≤r≤nmax​{min(al…r​)×sum(bl…r​)} 。

Where min(a) means the minimal value of every element of sequence a, sum(a) means the sum of every element of sequence a .

输入描述:

The first line contains an integer n .

The second line contains n integers meaning a1…na_{1 \dots n}a1…n​ .

The third line contains n integers meaning b1…nb_{1 \dots n}b1…n​ .

输出描述:

An integer meaning the answer.

示例1

输入

复制

3
1 -1 1
1 2 3

输出

复制

3

备注:

For all test datas, 1≤n≤3×106,−106≤ai,bi≤1061 \leq n \leq 3 \times 10^6,-10^6 \leq a_i,b_i \leq 10^61≤n≤3×106,−106≤ai​,bi​≤106.

题目大意: 给出一个数组a,与数组b,求在某个区间内,a的最小值*b数组在这个区间内的和,所有区间该值最大值.

题目思路:考虑单调栈,求出毎一个数c可作为最小值的区间[x,y],求出这个区间之后我们就可以在这个区间里,控制b的sum和,如果该数是个负数,那么我们就让包含该数c并且在该数控制范围内的sum和尽可能的小,因为负数*小的才会变大.否则如果该数为正数,我们就在[x,y]内找出一段包含c并且最大的和,正数*大数会变大.

所以我们开始预处理:我们思考如何处理包含该数并且在该数能控制范围内的最大最小和,首先我们可以想到,需要有两个值,一个是最大和,另一个是最小和(因为有正负之分),首先有一种做法,每一次到一个数我们就可以,向右求最大和向左求最大和[DP思路](或最小和),但是如果控制范围很大的话,这个复杂度就有点高了.所以我们考虑如何进行预处理.

我们首先从左到右,跑一遍当前位置的最大和(最小和),再从右到左跑一遍当前位置的最大和(最小和),{用DP的思想跑}:

状态转移方程 :

dp[i]=max(dp[i-1]+num[i],num[i])   dp[i]=min(dp[i-1]+num[i],num[i])   (从左到右)

对于毎一个数而言,他的最大最小和即为 dp[i](左)+dp[i]右-num[i].(以下全用最大和为例)

求出控制最大和之后,我们还需要要做一件事就是 要把控制最大的端点求出来,作用是:如果当前区间的最大和左右端点都比区间最小值小,那么我们就可以直接用这个值*num[i]即可.但是如果有小于左端点或者大于右端点的情况,我们需要把之外的减去,假设当前左端点小于最小值控制左端点,那么小于最小值控制的左端点的那一部分就应该被删除,因为这是连续又是DP思路写,那么最大值就截止到最小值控制的左端点l,右端点也一样.所以我们为了方便减去 部分和 我们用 前缀和维护一下.然后判断左端点和右端点,不符合就减去:


            ll S=dp3[i]+dp4[i]-num2[i];//先求当前最大和
            if(posp1[i]<pre[i]+1)//判断是否小于当前最小值控制的点
                S-=sum[pre[i]]-sum[posp1[i]-1];//减去即可
            if(posc1[i]>cur[i]-1)
                S-=sum[posc1[i]]-sum[cur[i]-1];
            maxl=max(maxl,num1[i]*S);//比较

然后还有两个细节,第一个DP决定他的最大最小值的端点,我们只需要判断一下即可:

    for(int i=1;i<=n;i++)
    {
        dp1[i]=max(dp1[i-1]+num2[i],num2[i]);
        if(dp1[i]==dp1[i-1]+num2[i]) posp[i]=posp[i-1];//如果与之前合并,那么他的左端点等于之前点的左端点
        else if(dp1[i]==num2[i])  posp[i]=i;
    }

还有就是单调栈维护区间最小值可控范围,这个之前博客里有过:单调栈讲解

最后,根据自己的需要决定数组,我是每一步都用一个数组来标记,不容易混,具体数组含义附在代码里,本以为会内存超限结果并没有啊哈hiahia:

/*
AshGuang
语言：C++ 代码长度：2326 运行时间： 1620 ms 占用内存：315016K
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e15+5;
const int maxn=3e6+8;
const double PI=acos(-1);
const ll mod=1e9+7;
ll n,m;
ll dp1[maxn],dp2[maxn],dp3[maxn],dp4[maxn];//分别维护 左最大 右最大 左最小 右最小
int st[maxn];//单调栈
ll pre[maxn],cur[maxn];//单调栈控制左右端点
ll num1[maxn],num2[maxn],posp[maxn],posc[maxn],posp1[maxn],posc1[maxn];
//数组a,数组b,最大和左端点,最大和右端点,最小和左端点,最小和右端点
ll sum[maxn];
void solve_dp()
{
    posc[0]=1;
    for(int i=1;i<=n;i++)
    {
        dp1[i]=max(dp1[i-1]+num2[i],num2[i]);
        if(dp1[i]==dp1[i-1]+num2[i]) posp[i]=posp[i-1];
        else if(dp1[i]==num2[i])  posp[i]=i;
    }
    posc[n+1]=n;
    for(int i=n;i>=1;i--)
    {
        dp2[i]=max(dp2[i+1]+num2[i],num2[i]);
        if(dp2[i]==dp2[i+1]+num2[i]) posc[i]=posc[i+1];
        else if(dp2[i]==num2[i])  posc[i]=i;
    }
    posp1[0]=1;
    for(int i=1;i<=n;i++)
    {
        dp3[i]=min(dp3[i-1]+num2[i],num2[i]);
        if(dp3[i]==dp3[i-1]+num2[i]) posp1[i]=posp1[i-1];
        else if(dp3[i]==num2[i])  posp1[i]=i;
    }
    posc1[n+1]=n;
    for(int i=n;i>=1;i--)
    {
        dp4[i]=min(dp4[i+1]+num2[i],num2[i]);
        if(dp4[i]==dp4[i+1]+num2[i]) posc1[i]=posc1[i+1];
        else if(dp4[i]==num2[i])  posc1[i]=i;
    }
}
void get_min()
{
    int s=0;
    st[0]=0;
    for(int i=1;i<=n;i++)
    {
        while(s&&num1[i]<=num1[st[s]]) s--;
        pre[i]=st[s];
        st[++s]=i;
    }
    st[0]=n+1;
    s=0;
    for(int i=n;i>=1;i--)
    {
        while(s&&num1[i]<=num1[st[s]]) s--;
        cur[i]=st[s];
        st[++s]=i;
    }
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&num1[i]);
    for(int i=1;i<=n;i++) {scanf("%lld",&num2[i]);sum[i]=sum[i-1]+num2[i];}
    solve_dp();
    get_min();
    ll maxl=-INF;
    for(int i=1;i<=n;i++)
    {
        if(num1[i]<0)
        {
            ll S=dp3[i]+dp4[i]-num2[i];
            if(posp1[i]<pre[i]+1)
                S-=sum[pre[i]]-sum[posp1[i]-1];
            if(posc1[i]>cur[i]-1)
                S-=sum[posc1[i]]-sum[cur[i]-1];
            maxl=max(maxl,num1[i]*S);
        }
        else
        {
            ll S=dp1[i]+dp2[i]-num2[i];
            if(posp[i]<pre[i]+1)
                S-=sum[pre[i]]-sum[posp[i]-1];
            if(posc[i]>cur[i]-1)
                S-=sum[posc[i]]-sum[cur[i]-1];
            maxl=max(maxl,num1[i]*S);
        }
    }
    printf("%lld\n",maxl);
    return 0;
}

总结:之前南昌的题,之前没有过,现在也终于算过了,记住单调栈的用处!!还有DP思路!