传送门 https://vjudge.net/problem/HDU-5696
一道比较基础的分治题...... 但是我似乎不会分治......
首先, 区间的价值肯定与最小值有关, 所以对于当前处理的区间, 我们首先暴力的求出区间的最小值, 其位置记为 pos. 之后...... 对于一个横跨过 pos 的区间, 它的价值必定可以由 pos 左右两边区间的价值更新而来, 所以说我们只需要暴力的在左右两边 O(n) 的扫一遍求出相应的长度的区间价值最大值, 之后用较短的区间的价值更新较长的即可.
之后再递归分治 pos 的左右两边的区间即可.
本题的关键在于, 能通过找到 pos 这个位置, 之后把横跨过 pos 的区间的值由左右两边更新. 但是其实这个方法挺不稳定的 orzzzz, 幸好都是随机数据, 能过......
看一下代码.
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- #include<iostream>
- #include<cmath>
- #include<set>
- #include<queue>
- #include<vector>
- #include<map>
- #define rep(i,a,n) for(int i = a;i <= n;i++)
- #define per(i,n,a) for(int i = n;i>= a;i--)
- #define enter putchar('\n')
- #define fr friend inline
- #define y1 poj
- #define mp make_pair
- #define pr pair<int,int>
- #define fi first
- #define sc second
- #define pb push_back
- #define lowbit(x) x & (-x)
- using namespace std;
- typedef long long ll;
- const int M = 200005;
- const int INF = 1000000009;
- const double eps = 1e-7;
- ll read()
- {
- ll ans = 0,op = 1;
- char ch = getchar();
- while(ch <'0' || ch> '9')
- {
- if(ch == '-') op = -1;
- ch = getchar();
- }
- while(ch>= '0' && ch <= '9')
- {
- ans *= 10;
- ans += ch - '0';
- ch = getchar();
- }
- return ans * op;
- }
- ll n,a[M],pos,tmp[M],ans[M];
- void solve(ll l,ll r)
- {
- if(l> r) return;
- ll len = r - l + 1,pos = l,cur = 0;
- rep(i,1,len) tmp[i] = 0;
- rep(i,l,r) if(a[i] < a[pos]) pos = i;
- rep(i,l,pos) tmp[pos - l + 1] = max(tmp[pos - l + 1],a[i] * a[pos]);
- rep(i,pos+1,r) tmp[r - pos + 1] = max(tmp[r - pos + 1],a[i] * a[pos]);
- rep(i,1,len)
- {
- cur = max(cur,tmp[i]);
- ans[i] = max(ans[i],cur);
- }
- solve(l,pos-1),solve(pos+1,r);
- }
- int main()
- {
- while(scanf("%lld",&n) != EOF)
- {
- rep(i,1,n) a[i] = read();
- solve(1,n);
- rep(i,1,n) printf("%lld\n",ans[i]);
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2876639.html