MT3046 愤怒的象棚

思路：

a[]存愤怒值；b[i]存以i结尾的，窗口里的最大值；c[i]存以i结尾的，窗口里面包含✳的最大值。

（✳为新大象的位置）

例：1 2 3 4 ✳ 5 6 7 8 9

则ans的计算公式=b3+b4+c4+c5+c6+b7+b8+b9;

b3为max[1 2 3];  b4为max[2 3 4];

c4为max[3 4 ✳]; c5为max[4 ✳ 5]; c6为max[✳ 5 6];

b7为max[5 6 7]; b8为max[6 7 8]; b9为max[7 8 9];

由此可以归纳得到一个公式：n个数，每个窗口长度为m，遍历到i时，ans可以分成三段：①[b(m)+b(m+1)+...+b(i-1)] + ②[c(i-1)+c(i)+...+c(i+m-2)] + ③[b(i+m-1)+...+b(n)]

（求max[]使用单调队列来求，求ans用前缀和）

ans=sumb[i-1]+sumc[i+m-2]-sumc[i-2]+sumb[n]-sumb[i+m-2]

但是还有ans某部分不存在的情况：

当i<=m时，此时①不存在，即ans=sumc[i+m-2]+sumb[n]-sumb[i+m-2]

若i>=n-m+2时，此时③不存在，，即ans=sumb[i-1]+sumc[n]-sumc[i-2]

当i>m&&i<n-m+2时，ans=sumb[i-1]+sumc[i+m-2]-sumc[i-2]+sumb[n]-sumb[i+m-2]

代码：

 

#include <bits/stdc++.h>
using namespace std;
const int N = 5e6 + 10;
int n, m, A, ans = 0;
int a[N], b[N], c[N];
int sumc[N], sumb[N];
void getmax(int n, int m)
{deque<int> q;for (int i = 1; i <= n; i++){if (!q.empty() && q.front() <= i - m)q.pop_front();while (!q.empty() && a[i] >= a[q.back()])q.pop_back();q.push_back(i);if (i >= m){b[i] = a[q.front()];sumb[i] = sumb[i - 1] + b[i];}}
}
void getmax2(int n, int m)
{deque<int> q;for (int i = 1; i <= n; i++){if (!q.empty() && q.front() <= i - m)q.pop_front();while (!q.empty() && a[i] >= a[q.back()])q.pop_back();q.push_back(i);if (i >= m){c[i] = max(A, a[q.front()]);sumc[i] = sumc[i - 1] + c[i];}}
}int main()
{cin >> n >> m >> A;for (int i = 1; i <= n; i++){cin >> a[i];}getmax(n, m);      // 求b[]getmax2(n, m - 1); // 求c[]for (int i = 1; i <= n + 1; i++){if (i <= m){ans = max(ans, sumc[i + m - 2] + sumb[n] - sumb[i + m - 2]);}else if (i >= n - m + 2){ans = max(ans, sumb[i - 1] + sumc[n] - sumc[i - 2]);}else{ans = max(ans, sumb[i - 1] + sumc[i + m - 2] - sumc[i - 2] + sumb[n] - sumb[i + m - 2]);}}cout << ans;return 0;
}