区间顺序枚举 hdu5696 区间的价值

区间的价值

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,那么该区间的长度为(RL+1)

现在聪明的杰西想要知道,对于长度为k的区间,最大价值的区间价值是多少。

当然,由于这个问题过于简单。

我们肯定得加强一下。

我们想要知道的是,对于长度为1n的区间,最大价值的区间价值分别是多少。

样例解释:

长度为1的最优区间为22 答案为66

长度为2的最优区间为45 答案为44

长度为3的最优区间为24 答案为26

长度为4的最优区间为25 答案为26

长度为5的最优区间为15 答案为16
 

Input
多组测试数据

第一行一个数n(1n100000)

第二行n个正整数(1ai109),下标从1开始。

由于某种不可抗力,ai的值将会是1109随机产生的一个数。(除了样例)
 

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 区间的价值