区间的价值
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 685 Accepted Submission(s): 343
Problem Description
我们定义“区间的价值”为一段区间的最大值*最小值。
一个区间左端点在 L，右端点在 R，那么该区间的长度为 (R−L+1)。
现在聪明的杰西想要知道，对于长度为 k的区间，最大价值的区间价值是多少。
当然，由于这个问题过于简单。
我们肯定得加强一下。
我们想要知道的是，对于长度为 1∼n的区间，最大价值的区间价值分别是多少。
样例解释：
长度为 1的最优区间为 2−2 答案为 6∗6
长度为 2的最优区间为 4−5 答案为 4∗4
长度为 3的最优区间为 2−4 答案为 2∗6
长度为 4的最优区间为 2−5 答案为 2∗6
长度为5的最优区间为 1−5 答案为 1∗6
一个区间左端点在 L，右端点在 R，那么该区间的长度为 (R−L+1)。
现在聪明的杰西想要知道，对于长度为 k的区间，最大价值的区间价值是多少。
当然，由于这个问题过于简单。
我们肯定得加强一下。
我们想要知道的是，对于长度为 1∼n的区间，最大价值的区间价值分别是多少。
样例解释：
长度为 1的最优区间为 2−2 答案为 6∗6
长度为 2的最优区间为 4−5 答案为 4∗4
长度为 3的最优区间为 2−4 答案为 2∗6
长度为 4的最优区间为 2−5 答案为 2∗6
长度为5的最优区间为 1−5 答案为 1∗6
Input
多组测试数据
第一行一个数 n(1≤n≤100000)。
第二行 n个正整数 (1≤ai≤109)，下标从 1开始。
由于某种不可抗力， ai的值将会是 1∼109内<b style="color:red;">随机产生</b>的一个数。（除了样例）
第一行一个数 n(1≤n≤100000)。
第二行 n个正整数 (1≤ai≤109)，下标从 1开始。
由于某种不可抗力， ai的值将会是 1∼109内<b style="color:red;">随机产生</b>的一个数。（除了样例）
Output
输出共 n行，第 i行表示区间长度为 i的区间中最大的区间价值。
Sample Input
5 1 6 2 4 4
Sample Output
36 16 12 12 6 【题意】中文题面。 【分析&解题思路】这道题上来看到感觉很不好做啊。要枚举所有的区间维护区间的最大值和最小值显然是不合理的。那么这道题该用什么办法呢？维护区间最大值和最小值可 以用RMQ或者线段树来完成。然后枚举每一个点为最小值，然后还要维护一个东西。那就是每个点可以左右延伸的最大范围，然后当前答案为ans[r-l+1]=max(ans[r-l+1], RMQ_MAX(l,r)*A[i])；然后维护出来的并不是最后的答案，想一下为什么？假设当前的ans是一个区间长度curlen的最佳答案，那么区间长度<curlen的答案肯定是>=ans 的。所以这里逆序递推就可以得到答案了。这里说得不清楚的话，我举个例子，比如1,2,3,4长度为3的最佳答案肯定是8，那么长度为2的答案是12>8，1,3,2,4也是如此。 因为我们定了一个最大值之后，只需要找一个最小值最大的值就行了，而长度越短，松弛空间更加的大！ 【PS这里贴一份别人用这种方法做的AC代码】 【来源:http://blog.csdn.net/queuelovestack/article/details/51476288】 【代码】
【解法二】这题还有一种更加奇妙的解法，贪心！我在第一种解法中已经提到过了，如果枚举当前的值为最大值的话，那么我们选择最小值，要让最小值最小的话，就可以得到
更优秀的答案。
【AC代码】
【补充】经过我在hdoj上测试，这两种方法的测试时间完全一样。说明贪心在这题还是很快的。
【加油，加油，加油】
const int N = 100005;
const int M = 40;
const int inf = 100000000;
const int mod = 2009;
int s[N],n,maxnum[N][20],l[N],r[N];
__int64 ans[N];
void RMQ() //预处理 O(nlogn)
{
int i,j;
int m=(int)(log(n*1.0)/log(2.0));
for(i=1;i<=n;i++)
maxnum[i][0]=s[i];
for(j=1;j<=m;j++)
for(i=1;i+(1<<j)-1<=n;i++)
maxnum[i][j]=max(maxnum[i][j-1],maxnum[i+(1<<(j-1))][j-1]);
}
int Ask_MAX (int a,int b) //O(1)
{
int k=int(log(b-a+1.0)/log(2.0));
return max(maxnum[a][k],maxnum[b-(1<<k)+1][k]);
}
int main()
{
int i,k;
while(~scanf("%d",&n))
{
memset(ans,0,sizeof(ans));
for(i=1;i<=n;i++)
{
scanf("%d",&s[i]);
l[i]=r[i]=i;
}
RMQ();
for(i=2;i<=n;i++)
{
k=i-1;
while(s[i]<=s[k])
k=l[k]-1;
l[i]=k+1;
}
for(i=n-1;i>0;i--)
{
k=i+1;
while(s[i]<=s[k])
k=r[k]+1;
r[i]=k-1;
}
for(i=1;i<=n;i++)
ans[r[i]-l[i]+1]=max(ans[r[i]-l[i]+1],(__int64)Ask_MAX(l[i],r[i])*s[i]);
for(i=n-1;i>0;i--)
ans[i]=max(ans[i+1],ans[i]);
for(i=1;i<=n;i++)
printf("%I64d\n",ans[i]);
}
return 0;
} 【解法二】这题还有一种更加奇妙的解法，贪心！我在第一种解法中已经提到过了，如果枚举当前的值为最大值的话，那么我们选择最小值，要让最小值最小的话，就可以得到
更优秀的答案。
【AC代码】
//Cloud , you are my sunshine!
//I can't live without you!
//You are the most beautiful girl in the world!
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn=100005;
int a[maxn];
LL ans[maxn];
int n;
int main(){
while(~scanf("%d",&n)){
memset(ans,0,sizeof(ans));
for(int i=1; i<=n; i++) scanf("%d",&a[i]);
LL maxx,minn;
for(int i=1; i<=n; i++){//枚举最大值,贪心取次大
int l=i,r=i,curlen=1;
maxx=minn=a[i];
while(1){
ans[curlen]=max(ans[curlen],maxx*minn);
//只能向右扩展
if(l==1||a[l-1]>maxx){
if(a[r+1]>maxx) break;
else if(r==n) break;
else{
r++;
curlen++;
if(a[r]<minn) minn=a[r];
}
}
//可以向右也可以向左扩展
else{
if(r==n||a[r+1]>maxx){//只能向左扩展
l--;
curlen++;
if(a[l]<minn) minn=a[l];
}
else{
if(a[l-1]>a[r+1]){
l--;
curlen++;
if(a[l]<minn) minn=a[l];
}
else
{
r++;
curlen++;
if(a[r]<minn) minn=a[r];
}
}
}
}
}
for(int i=1; i<=n; i++){
printf("%I64d\n",ans[i]);
}
}
return 0;
}
【补充】经过我在hdoj上测试，这两种方法的测试时间完全一样。说明贪心在这题还是很快的。
【加油，加油，加油】
京公网安备 11010502036488号