感觉每一步都挺自然的。
首先连续加减让我们不难想到差分，每次给 \(d_i\) 加一或减一，每次给 \(d_{i+l}\) 减一或加一。
然后要求单调不降就是要求每个 \(d_i\) 大于等于 \(0\)。
然后注意到我们每次操作相当于是 \(i\) 向 \(i+l\) 贡献 \(1\) 或者 \(i+l\) 向 \(i\) 贡献 \(1\)，结合数据范围让我们想到网络流。
具体的，我们可以从起点给每个 \(i\) 连一条流量为 \(V+d_i\)，然后每个 \(i\) 向终点连一条流量为 \(V\) 的边，就能让每个 \(d_i\) 尽可能大于等于 \(0\) 了，然后刚刚的贡献转移我们在网络上直接连边即可，再将费用变成代价 \(c\)，就可以跑费用流啦！
代码：
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; ++ i)
#define rrp(i, l, r) for (int i = r; i >= l; -- i)
#define pii pair <int, int>
#define eb emplace_back
#define inf 1000000000
#define id(x, y) m * (x - 1) + y
#define ls p << 1
#define rs ls | 1
using namespace std;
constexpr int N = 1e6 + 5, M = 105, P = 998244353;
constexpr double PI = acos (-1.0);
inline int rd () {
int x = 0, f = 1;
char ch = getchar ();
while (! isdigit (ch)) {
if (ch == '-') f = -1;
ch = getchar ();
}
while (isdigit (ch)) {
x = (x << 1) + (x << 3) + ch - 48;
ch = getchar ();
}
return x * f;
}
int n, m, k, s, t;
vector <int> vec;
int tot, cnt = 1;
int h[N], to[N], cap[N], nxt[N], cost[N];
int a[N];
void add (int u, int v, int w, int c) {
to[++ cnt] = v;
cap[cnt] = w;
cost[cnt] = c;
nxt[cnt] = h[u];
h[u] = cnt;
to[++ cnt] = u;
cap[cnt] = 0;
nxt[cnt] = h[v];
cost[cnt] = - c;
h[v] = cnt;
}
int incf[N], dis[N], pre[N];
bool vis[N];
queue <int> q;
int spfa () {
q.push (s);
rep (i, s, t) incf[i] = 0, dis[i] = inf;
dis[s] = 0, incf[s] = inf;
while (! q.empty ()) {
int u = q.front ();
q.pop ();
for (int i = h[u]; i; i = nxt[i]) {
int v = to[i], w = cap[i], c = cost[i];
if (! w) continue;
if (dis[u] + c < dis[v]) {
dis[v] = dis[u] + c;
pre[v] = i;
incf[v] = min (w, incf[u]);
q.push (v);
}
}
}
return incf[t];
}
int MCMF () {
int mincost = 0, maxflow = 0;
while (spfa ()) {
maxflow += incf[t];
mincost += incf[t] * dis[t];
int u = t;
while (u != s) {
int i = pre[u];
cap[i] -= incf[t];
cap[i ^ 1] += incf[t];
u = to[i ^ 1];
}
}
if (maxflow != (n + 1) * 1000) return -1;//一定要记得判无解
return mincost;
}
int main () {
// freopen ("1.in", "r", stdin);
// freopen ("1.out", "w", stdout);
cin >> n >> m;
rep (i, 1, n) cin >> a[i];
rrp (i, 2, n) a[i] -= a[i - 1];
t = n + 2;
a[n + 1] = 1000000;
rep (i, 1, n + 1) add (s, i, a[i] + 1000, 0), add (i, t, 1000, 0);
rep (i, 1, m) {
char ch;
int l, c;
cin >> ch >> l >> c;
rep (j, 1, n - l + 1) {
if (ch == '+') add (j + l, j, inf, c);
else add (j, j + l, inf, c);
}
}
cout << MCMF ();
}