题目链接[http://poj.org/problem?id=2796]
题意：给出一个数列，要求在这个数列里找到一个区间，使得在这个区间里的最小值*SUM[l,r]最大。
题解：思路来源于【http://acm.hdu.edu.cn/showproblem.php?pid=1506】这个题。思想是：一a[i]为某个区间的最小值，初始区间为[i,i],左端向左延伸，右端向右延伸。最后维护最大值。
但是向前向后延伸的时候不能暴力，时间不允许，这里要用到DP的思想：
定义L[MAXN]=R[MAXN]=i;对于a[i]的L[i]，刚开始的L[i]=i;如果a[i]>a[L[i]-1] -> L[i]=L
---恢复内容结束---
题目链接[http://poj.org/problem?id=2796]
题意：给出一个数列，要求在这个数列里找到一个区间，使得在这个区间里的最小值*SUM[l,r]最大。
题解：思路来源于【http://acm.hdu.edu.cn/showproblem.php?pid=1506】这个题。思想是：一a[i]为某个区间的最小值，初始区间为[i,i],左端向左延伸，右端向右延伸。最后维护最大值。
但是向前向后延伸的时候不能暴力，时间不允许，这里要用到DP的思想：
定义L[MAXN]=R[MAXN]=i;对于a[i]的L[i]，刚开始的L[i]=i;如果a[i]>a[L[i]-1] -> L[i]=L[L[i]-1];2、R同理。
#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); }
原文：http://www.cnblogs.com/pealicx/p/6270632.html