UVa 1619 – Feel Good

点击打开UVa题目链接

题意

给出一个长度为n的正整数序列ai，求出一段连续子序列al~ar，使得sum(al~ar)*min(al~ar)最大

分析

对于每个数字ai，当他作为最小值时有最优解当且仅当l，r分别取到大于等于ai的最左和最右边。递归找出这样的边界，然后枚举最小值求出最优解即可。

CPP代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 102400;
int kase, n, v[maxn],l[maxn], r[maxn];
ll sum[maxn];

void input() {
    for(int i = 1; i <= n; ++i) {
        cin >> v[i];
        sum[i] = sum[i-1] + v[i];
        l[i] = r[i] = i;
    }
    v[0] = v[n+1] = -1;
    for(int i = n; i >= 1; --i)
        while(v[r[i]+1] >= v[i])
            r[i] = r[r[i]+1];
    for(int i = 1; i <= n; ++i)
        while(v[l[i]-1] >= v[i])
            l[i] = l[l[i]-1];
}

void solve() {
    ll best = 0, L = 1, R = 1;
    for(ll i = 1; i <= n; ++i) {
        ll cur = v[i] * (sum[r[i]] - sum[l[i]-1]);
        if(cur > best) {
            best = cur;
            L = l[i], R = r[i];
        }
    }
    cout << best << endl << L << " " << R << endl;
}

int main() {
    ios::sync_with_stdio(false);
    while(cin >> n) {
        if(kase++) cout << endl;
        input();
        solve();
    }
    return 0;
}