区间的价值
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 1293 Accepted Submission(s): 581
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内随机产生的一个数。(除了样例)
第一行一个数n(1≤n≤100000)。
第二行n个正整数(1≤ai≤109),下标从1开始。
由于某种不可抗力,ai的值将会是1∼109内随机产生的一个数。(除了样例)
Output
输出共n行,第i行表示区间长度为i的区间中最大的区间价值。
Sample Input
5
1 6 2 4 4
Sample Output
36
16
12
12
6
//以a[i]为最大值,然后向两边扩展
#include
#include
#include
#define ll long long
using namespace std;
int n;
ll a[100005],dp[100005];
void solve() {
memset(dp,0,sizeof(dp));
for(int i=1; i<=n; ++i)
scanf("%lld",a+i);
for(int i=1; i<=n; ++i) {
dp[1]=max(dp[1],a[i]*a[i]);
int l=i,r=i;
ll mi=a[i];
while(1) {
if(ra[l-1])) mi=min(a[++r],mi);
else mi=min(a[--l],mi);
if(a[l]>a[i]||a[r]>a[i]) break;
dp[r-l+1]=max(dp[r-l+1],mi*a[i]);
if(r-l+1==n) break;
}
}
for(int i=1; i<=n; ++i)
printf("%lldn",dp[i]);
}
int main() {
while(~scanf("%d",&n))
solve();
return 0;
}
未经允许不得转载!区间顺序枚举 hdu5696 区间的价值