https://www.codetd.com/article/2798845
经过几个月辛勤的工作，FJ决定让奶牛放假。假期可以在1…N天内任意选择一段（需要连续），每一天都有一个享受指数W。但是奶牛的要求非常苛刻，假期不能短于P天，否则奶牛不能得到足够的休息；假期也不能超过Q天，否则奶牛会玩的腻烦。FJ想知道奶牛们能获得的最大享受指数。
Input
第一行：N,P,Q.
第二行：N个数字，中间用一个空格隔开,每个数都在longint范围内。
第二行：N个数字，中间用一个空格隔开,每个数都在longint范围内。
Output
一个整数，奶牛们能获得的最大享受指数。
Sample Input
5 2 4
-9 -4 -3 8 -6
-9 -4 -3 8 -6
Sample Output
5
Data Constraint
50% 1≤N≤10000
100% 1≤N≤100000
１<=p<=q<=n
Hint
选择第3-4天，享受指数为-3+8=5。
100% 1≤N≤100000
１<=p<=q<=n
Hint
选择第3-4天，享受指数为-3+8=5。
看到区间的问题首先肯定是想到求前缀和，我们把[1,k]的和记为sum[k]，可以得到sum[i] = sum[i - 1] + a[i]，[l,r]的和即为sum[r] - sum[l - 1]（这里视sum[0] = 0）。我们假设选择的区间为[l,r]且r固定，可知r−q+1≤l≤r−p+1r−q+1≤l≤r−p+1，若要使[l,r]区间的值最大，则sum[l - 1]需最小，才可使得sum[r] - sum[l - 1]最小，当i右移一位到i+1，因为p,q为给定不变的值，对应寻找最小sum[l-1]的区间也右移一位，与上题同。
如下图，当p=3,q=5时：
如下图，当p=3,q=5时：
关于单调队列的运用还有很多，例如斜率优化DP等等。总而言之，使用单调队列优化DP，那么必会有求i之前某个范围的极值的操作，这类DP的方程通常为：
F[i]=min(F[j]+a[i]:j<i)F[i]=min(F[j]+a[i]:j<i)
a[i]是与j无关的数。
F[i]=min(F[j]+a[i]:j<i)F[i]=min(F[j]+a[i]:j<i)
a[i]是与j无关的数。
int n,p,q,l,r,head = 1,tail = 0,ans = -2147483647;
int que[100001],a[100001];
long long sum[100001];
int max(long long a,long long b)
{
return a > b ? a : b;
}
int main()
{
sum[0] = 0;
scanf("%d %d %d", &n, &p, &q);
for (int i = 1;i <= n;i++)
{
scanf("%d", &a[i]);
sum[i] = sum[i-1] + a[i]; //记前缀和
}
for (r = p;r <= n;r++)
{
while (head <= tail && sum[que[tail]-1] >= sum[r-p]) tail--; //更优的sum[l - 1]予以插队
que[++tail] = r+1-p; //入队
while (head <= tail && que[head] < r+1-q) head++; //不处于维护范围内的出队
ans = max(ans, sum[r]-sum[que[head]-1]); //更新答案
}
printf("%d\n", ans);
return 0;
}
前缀和 + dp + 单调队列。
写了树状数组。。。。但是树状数组求区间和比前缀和要慢啊。。。
首先前缀和，sum[i] = sum[i - 1] + sum[i – 2];所以对于区间[i,j],区间和sum(i,j) = sum[j] – sum[i]，其中j – q <= i <= j – p;这时可以发现，若要sum(i,j)尽量大，那么=sum[i]要尽量小，这时要用单调递增队列维护i的区间，队列中存sum数组的下标。
单调队列满足两个性质：
1.单调队列必须满足从队头到队尾的严格单调性。
2.排在队列前面的比排在队列后面的要先进队。
元素进队列的过程对于单调递增队列，对于一个元素a 如果 a > 队尾元素，那么直接将a扔进队列；如果 a <= 队尾元素 则将队尾元素出队列，直到满足 a 大于队尾元素即可。
枚举j从p到n，即枚举右端点，对于每个枚举的右端点，更新单调队列，首先要保证head始终<= tail，当队尾元素的值sum[que[tail]] > 当前要进队的元素的值sum[j – p]时，队尾的标记tail要前移，tail--；之后队尾元素更新为j – p；对于队首，要保证q[head] > j – q,所以head要++，直到满足。这样更新完成后，队首元素的值就是最小的了，此时在ans与sum[j] – sum[q[head]]间取max。
动态规划，先求一个前缀和sum，ans=max(ans,sum[i]-sum[k])(i-p<=k<=i-q)
根据上式，若ans最大，则sum[k]尽量小，所以单调队列维护区间i-q~i-p的最小值即可。
根据上式，若ans最大，则sum[k]尽量小，所以单调队列维护区间i-q~i-p的最小值即可。
lon n,P,Q,ans=inf,tmp,sum[maxn];
lon head=1,tail,q[maxn];
int main()
{
cin>>n>>P>>Q;
for(int i=1;i<=n;i++)
{
cin>>tmp;
sum[i]=sum[i-1]+tmp;
}
for(int i=P;i<=n;i++)
{
while(head<=tail&&sum[i-P]<sum[q[tail]])
tail--;
q[++tail]=i-P;
while(head<=tail&&q[head]<i-Q)
head++;
ans=max(ans,sum[i]-sum[q[head]]);
}
cout<<ans;
return 0;
}
单调队列 - 有限制的最大和问题
scanf("%d%d%d",&n,&p,&q);
for(int i=1; i<=n; i++)
{
scanf("%lld",&num[i]);
num[i]+=num[i-1];
}
int ans=0x80000000;
std::deque<int> deq; //单调队列
//保存假期的起始点
//单调队列往往保存的是下标
for(int i=p; i<=n; i++)
{
//单调队列第一步：删去非最优解
//这一步最重要
//对于本题而言，如果把之前的数作为起始点还不如把当前点作为起始点，那就删了它
//如果前几个数的和比i-p对应的数还要大，说明num[j]-num[i-p]比num[j]-num[前几个数]要大
while(!deq.empty() && num[deq.back()] > num[i-p])
deq.pop_back();
//单调队列第二步：保存当前解
deq.push_back(i-p); //保存起始位置
//单调队列第三步：删去过时解
//这一步可以放在任何位置，但必须放在更新答案前
while(!deq.empty() && deq.front() < i-q)
deq.pop_front();
//单调队列第四步：更新答案
//答案读取的是front，因为根据之前的操作front是最优解
ans=std::max(ans,int(num[i]-num[deq.front()]));
}
printf("%d",ans);
int main()
{
scanf("%lld %lld %lld", &n, &p, &Q);
rep(i,1,n) scanf("%lld", &a),sum[i] = a + sum[i-1];
rep(i,p,n)
{
while(sum[q[tail]] >= sum[i-p] && head <= tail) tail--;//因为i-p处的元素必须入队，所以队中一切比sum[i-p]大的元素必须出队
q[++tail] = i - p;//把sum[i-p]压入队列
while(q[head] < i - Q) head++;//因为我们最多只能取到i-q这么长的区间，所以在这个区间之前的所有元素必须出列。
f[i] = sum[i] - sum[q[head]];
ans = max(ans, f[i]);
}
printf("%lld\n", ans);
return 0;
}
X.
1.线段树 复杂度（nlogn）
2.单调队列 复杂度（n）
具体实现
1.线段树：
首先预处理出来sum前缀和，
对于每一点i，我们只需要找到符合题意范围内最小的即可
并放入线段树中
对去查询每一个点，用线段树去查询i-q+1~i-p+1之间的最小值
然后去更新最大值
2.单调队列：
构造一个单调队列
当枚举到i的时候，用sum[i-p+1]去更新队列
首先，我们想一想怎么算每个“几天内”的最大值，首先想可以暴力，枚举一次天数，再枚举一次i，时间是 O(n2)，爆了。
所以我们还要想一想。
前缀和？可以优化……
线段树？能考虑……
这几个小想法组合起来就可以了，但是好像不是很好想。
我们可以枚举第一个休息日的编号i，我们要算从这个第i天开始，往后的P到Q天里快乐指数最大那一天快乐指数是多少，枚举过后取个max就行了。
按这种方式算的话，如何将时间复杂度优化到最小？
考虑前缀和和线段树。
前缀和数组pre维护的是的快乐指数之和，线段树求的是i+P-1 ~ i+Q-1这一段区间的快乐指数前缀和最大值maxn,我们发现maxn-pre[i]就是从这个第i天开始，往后的P到Q天里快乐指数最大那一天快乐指数是多少。
其实求最大值的部分，用st表或者其他的也行，只不过我觉得线段树更好。
总共的复杂度就是O(nlogn)
所以我们还要想一想。
前缀和？可以优化……
线段树？能考虑……
这几个小想法组合起来就可以了，但是好像不是很好想。
我们可以枚举第一个休息日的编号i，我们要算从这个第i天开始，往后的P到Q天里快乐指数最大那一天快乐指数是多少，枚举过后取个max就行了。
按这种方式算的话，如何将时间复杂度优化到最小？
考虑前缀和和线段树。
前缀和数组pre维护的是的快乐指数之和，线段树求的是i+P-1 ~ i+Q-1这一段区间的快乐指数前缀和最大值maxn,我们发现maxn-pre[i]就是从这个第i天开始，往后的P到Q天里快乐指数最大那一天快乐指数是多少。
其实求最大值的部分，用st表或者其他的也行，只不过我觉得线段树更好。
总共的复杂度就是O(nlogn)
