HDU5696 区间的价值

传送门

一句话题意:求1~n长度区间最大值与最小值之乘积的最大值(保证数据随机)

Time cost: 45min

Solution:

比较基本的题

首先统计答案可以针对每个点更新所有长度这样可以单调

然后...然后就不会了

发现是数据随机所以可以乱搞

对于每个点作为最大值类似尺取法的方式更新最小值和答案

这样一般情况下复杂度随数据波动性变化单调性越强越凉

Code:

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<queue>
 6 #include<iostream>
 7 #define B puts("GGGGGGG");
 8 #define ms(a,b) memset(a,b,sizeof a)
 9 #define rep(i,a,n) for(int i = a;i <= n;i++)
10 #define per(i,n,a) for(int i = n;i >= a;i--)
11 #define inf 2147483647
12 using namespace std;
13 typedef long long ll;
14 ll read() {
15     ll as = 0,fu = 1;
16     char c = getchar();
17     while(c < '0' || c > '9') {
18         if(c == '-') fu = -1;
19         c = getchar();
20     }
21     while(c >= '0' && c <= '9') {
22         as = as * 10 + c - '0';
23         c = getchar();
24     }
25     return as * fu;
26 }
27 const int N = 110003;
28 //head
29 int n;
30 ll a[N],dp[N];
31 int main() {
32     // freopen("in.in","r",stdin);
33     while(~scanf("%d",&n)) {
34         ms(dp,0);
35         rep(i,1,n) a[i] = read();
36         rep(i,1,n) {
37             dp[1] = max(dp[1],a[i] * a[i]);
38             int l = i,r = i;
39             ll minn = a[i];
40             while(1) {
41                 if(r-l+1 == n) break;
42                 if(l > 1 && (r == n || a[l-1] > a[r+1])) minn = min(minn,a[--l]);
43                 else minn = min(minn,a[++r]);
44                 if(a[l] > a[i] || a[r] > a[i]) break;
45                 dp[r-l+1] = max(dp[r-l+1],a[i] * minn);
46             }
47         }
48         rep(i,1,n) printf("%lld
",dp[i]);
49     }
50     return 0;
51 }