holiday

Description
经过几个月辛勤的工作，FJ 决定让奶牛放假。假期可以在1…N 天内任意选择一段（需要连续），每一天都有一个享受指数W。但是奶牛的要求非常苛刻，假期不能短于P 天，否则奶牛不能得到足够的休息；假期也不能超过Q 天，否则奶牛会玩的腻烦。FJ 想知道奶牛们能获得的最大享受指数。

Input(holiday.in)
第一行：N,P,Q.
第二行：N 个数字，中间用一个空格隔开。

Output(holiday.out)
一个整数，奶牛们能获得的最大享受指数。

Sample Input
5 2 4
-9 -4 -3 8 -6

Sample Output
5

Limitation
time:1s
memory:65536kb
50% 1≤N≤10000
100% 1≤N≤100000
１<=p<=q<=n

Hint
选择第3-4 天，享受指数为-3+8=5。

首先把题目简化一下，就是告诉你在第一天开始放假。

那么也就是说，奶牛们最早在第P天停止休假，最晚在第Q天停止休假。所以说我们要求的就是让sum[1, j] (P <= j <= Q)最大。

这就好办了，如果我们预处理出前缀和,这就转化成了RMQ问题，只要在前缀和数组上跑一遍st表，求出[P, Q]中的最大值就行了。

那么，如果告诉你在第i天开始放假呢？

那也没什么，只要用上述的方法求出ans后减去sum[i]就行了。

然而这道题并没有告诉你在哪一天开始放假。

怎么办？

很简单，枚举,取max。

枚举开始放假的时间第i天，如果开始预处理前缀和和st表的话，那么对于每一个i，查询就是O(1)，整体复杂度O(n).

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cmath>
 5 #include<cstring>
 6 #include<cctype>     
 7 using namespace std;
 8 typedef long long ll;
 9 #define enter printf("
")
10 const int maxn = 1e5 + 5; 
11 const int INF = 0x3f3f3f3f;
12 inline ll read()
13 {
14     ll ans = 0;
15     char ch = getchar(), last = ' ';
16     while(!isdigit(ch)) {last = ch; ch = getchar();}
17     while(isdigit(ch))
18     {
19         ans = ans * 10 + ch - '0'; ch = getchar();    
20     }
21     if(last == '-') ans = -ans;
22     return ans;
23 }
24 inline void write(ll x)
25 {
26     if(x < 0) {putchar('-'); x = -x;}
27     if(x == 0) {putchar('0'); return;}
28     int q[100], N = 0;
29     q[1] = 0;
30     while(x) {q[++N] = x % 10; x /= 10;}
31     while(N) {putchar('0' + q[N]); --N;}
32 }
33 
34 int n, l, r;
35 ll a[maxn], sum[maxn]; 
36 ll ans = (ll)-INF * INF;
37 
38 ll dp[maxn][30];                
39 int size[maxn];
40 void RMQ(int n)
41 {
42     for(int i = 1; i <= n; ++i) dp[i][0] = sum[i];
43     for(int j = 1; (1 << j) <= n; ++j)
44         for(int i = 1; i + (1 << j) - 1 <= n; ++i)
45             dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
46     int k = 0;
47     for(int i = 1; i <= n; ++i) 
48     {
49         if ((1 << k) <= i) k++; 
50         size[i] = k - 1;
51     }
52 }
53 ll query(int L, int R)
54 {
55     int k = size[R - L + 1];
56     return max(dp[L][k], dp[R - (1 << k) + 1][k]);
57 }
58 
59 int main()
60 {
61     freopen("holiday.in", "r", stdin);
62     freopen("holiday.out", "w", stdout);
63     n = read(); l = read(); r = read();
64     for(int i = 1; i <= n; ++i) {a[i] = read(); sum[i] = sum[i - 1] + a[i];}
65     RMQ(n);
66     for(int i = 1; i <= n - l; ++i)
67     {
68         int L = i + l, R = i + r;
69         if(R > n) R = n;
70         ll _ans = query(L, R) - sum[i];
71         ans = max(ans, _ans);
72     }
73     write(ans); enter;
74     return 0; 
75 }