Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM-ICPC竞赛训练》暑期课面向全球招生。容量有限,报名从速!

DP的思想

Posted by 5120155010 at 2017-01-10 20:00:29 on Problem 2796
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 100050;
LL a[MAXN], sum[MAXN];
LL L[MAXN], R[MAXN];
int n;
int main ()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i]);
        sum[i] = sum[i - 1] + a[i];
        L[i] = R[i] = i;
    }
    a[0] = a[n + 1] = -1;
    for(int i = 1; i <= n; i++)
    {
        while(a[i] <= a[L[i] - 1])
            L[i] = L[L[i] - 1];
    }
    for(int i = n; i >= 1; i--)
    {
        while(a[i] <= a[R[i] + 1])
            R[i] = R[R[i] + 1];
    }
    LL ans = -1, l, r;
    for(int i = 1; i <= n; i++)
    {
        LL T = a[i] * (sum[R[i]] - sum[L[i] - 1]);
        if(ans < T)
            ans = T, l = L[i], r = R[i];
    }
    printf("%lld\n%lld %lld\n", ans, l, r);
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator