首页 > 代码库 > UVa1619 Feel Good (标记,枚举)
UVa1619 Feel Good (标记,枚举)
链接：http://vjudge.net/problem/UVA-1619
分析：首先计算前缀和，后面会用到。设每个i都属于一个满足下述条件的最大区间（因为题意说是正整数序列，区间当然越大越好），a[i]为区间中的最小值，然后预处理出以i为轴向左和向右延伸的最远位置L[i]和R[i]来标记这个区间，最后就是O（n）的枚举。
1 #include <cstdio> 2 3 const int maxn = 1e5+5; 4 5 int n, a[maxn], L[maxn], R[maxn]; 6 long long prefix_sum[maxn]; 7 8 int main() { 9 int T = 0;10 while (scanf("%d", &n) == 1) {11 if (T++) printf("\n");12 a[0] = -1; a[n+1] = -1; prefix_sum[0] = 0;13 for (int i = 1; i <= n; i++) {14 scanf("%d", &a[i]);15 prefix_sum[i] = prefix_sum[i-1] + a[i];16 L[i] = i; R[i] = i;17 }18 for (int i = 1; i <= n; i++)19 while (a[i] <= a[L[i]-1]) L[i] = L[L[i]-1];20 for (int i = n; i >= 1; i--)21 while (a[i] <= a[R[i]+1]) R[i] = R[R[i]+1];22 long long ans = a[1] * a[1];23 int l = 1, r = 1;24 for (int i = 1; i <= n; i++) {25 long long v = (prefix_sum[R[i]] - prefix_sum[L[i]-1]) * a[i];26 if (v > ans || (v == ans && r-l > R[i]-L[i])) {27 ans = v;28 l = L[i], r = R[i];29 }30 }31 printf("%lld\n", ans);32 printf("%d %d\n", l, r);33 }34 return 0;35 }
UVa1619 Feel Good (标记,枚举)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。