| Time Limit: 3000MS | Memory Limit: 65536K | |
| Total Submissions: 22879 | Accepted: 6279 | |
| Case Time Limit: 1000MS | Special Judge |
Description
Input
Output
Sample Input
6 3 1 6 4 5 2
Sample Output
60 3 5
题意：给你一个n长度的数组，ans(l,r) 表示 sum l到r的和 * l 到 r子列中的最小值。求最大的ans，输出其和l，r
思路：前缀和预处理。
最开始的思路是用单调列维护（1 ~n）长度的移动框寻找最优解（TLE）
TLE代码：
#include <iostream> #include <cmath> #include <cstdio> #include <cstring> #include <string> #include <map> #include <iomanip> #include <algorithm> #include <queue> #include <stack> #include <set> #include <vector> //const int maxn = 1e5+5; #define ll long long #define inf 0x3f3f3f3f #define FOR(i,a,b) for( int i = a;i <= b;++i) #define bug cout<<"--------------"<<endl ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a/gcd(a,b)*b;} const int maxn = 110000; using namespace std; int a[maxn],sum[maxn]; struct node { int place,nub; }que[maxn]; int n; ll maxx = 0; ll l = 0; ll r = 0; //int que[maxn]; void solve(int k) { int tail = 0; int head = 1; for(int i = 1;i <= k-1; ++i) { while(que[tail].nub>=a[i] && tail>=head) { tail--; } tail++; que[tail].nub=a[i]; que[tail].place=i; } for(int i=k;i<=n;++i) { while(que[tail].nub>=a[i] && tail>=head) { tail--; } tail++; que[tail].nub=a[i]; que[tail].place=i; while(que[tail].place-que[head].place>=k) { head++; } //printf("%d ",que[head].nub); ll temp = que[head].nub * (sum[i] - sum[i-k]); // maxx = max(temp,maxx ); if(temp > maxx) { maxx = temp; l = i - k + 1; r = i; } } //printf("%I64d\n",maxx ); } int main() { //freopen("C:\\ACM\\input.txt","r",stdin); while(scanf("%d",&n) != EOF) { memset( sum,0 ,sizeof(sum)); maxx = 0; l = 1; r = 1; for(int i = 1;i <= n; ++i) { scanf("%d",a+i); sum[i] = sum[i-1] + a[i]; } for(int i = 1;i <= n; ++i) { solve(i); } //cout<<maxx<<endl<<l<<" "<<r<<endl; printf("%I64d\n",maxx ); printf("%I64d %I64d\n",l,r); } }
正确思路: 遍历每一个a[n]，寻找对于每一个a【n】，求出关于它为最小值的子列的左位置和右位置的大小并且存入数组 l【】 ，r【】中。最后再遍历跑一遍求的最优解
求的左位置和右位置只需要跑两次单调栈就ok了
#include <iostream> #include <cmath> #include <cstdio> #include <cstring> #include <string> #include <map> #include <iomanip> #include <algorithm> #include <queue> #include <stack> #include <set> #include <vector> //const int maxn = 1e5+5; #define ll long long #define inf 0x3f3f3f3f #define FOR(i,a,b) for( int i = a;i <= b;++i) #define bug cout<<"--------------"<<endl ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a/gcd(a,b)*b;} using namespace std; int a[1100000]; ll sum[1100000]; int l[1100000]; int r[1100000]; int n; ll maxx = 0; //int que[maxn]; int main() { //freopen("C:\\ACM\\input.txt","r",stdin); while(scanf("%d",&n) != EOF) { memset( sum,0 ,sizeof(sum)); for(int i = 1;i <= n; ++i) { scanf("%d",a+i); sum[i] = sum[i-1] + a[i]; } stack<int>sta; for(int i = 1;i <= n; ++i) { while(sta.size() && a[i] <= a[sta.top()]) sta.pop(); if(sta.size()) l[i] = sta.top() + 1; else l[i] = 1; sta.push(i); } while(sta.size()) sta.pop(); for(int i = n;i >= 1; --i) { while(sta.size() && a[i] <= a[sta.top()]) sta.pop(); if(sta.size()) r[i] = sta.top() - 1; else r[i] = n; sta.push(i); } //for(int i = 1;i <= n; ++i) cout<<l[i]<<" "<<r[i]<<endl; int ansl = 1; int ansr = 1; ll ans = 0; for(int i = 1;i <= n; ++i) { ll temp = a[i] * ( sum[r[i]] - sum[l[i]-1] ); if(temp > ans) { ans = temp; ansl = l[i]; ansr = r[i]; } } printf("%I64d\n",ans); printf("%d %d\n",ansl,ansr ); } }
原文：https://www.cnblogs.com/jrfr/p/11673161.html