题意

一个长度为 $n$ 的整数序列 $\{h_i\}$ ， $m$ 种操作，每种操作为花费一定的代价将一段长度为给定值的连续子区间加一或减一，每种操作都可以使用任意多次。

求把 $\{h_i\}$ 变成单调不降的最小代价，或者判断无解。

$n,m\leq200$ 。

思路

区间加一减一，用差分维护，设差分数组 $a_i=h_i-h_{i-1}$ 。那么目标就是要使所有 $a_i\geq0$ 。

考虑网络流建模，所有满足 $a_i<0$ 的点向汇点连边，容量为 $−a_i$ ，费用为 $0$ ；源点向其他点连边，容量为 $a_i$ ，费用为 $0$ （特殊地，源点向 $1$ 和 $n+1$ 连容量为 $+\infty$ 的边）

每次操作连 $r$ 到 $l$ 的边，容量 $+\infty$ ，费用为 $c$ 。

如果通向汇点的边不满流，则无解。

代码

#define INF 0x3f3f3f3f3f3f3f3f

const int N = 250;
const int M = N * N * 20;
const int inf = 1e8;
struct node {
	ll x, w, to, nxt, op;
}e[M];
ll n, m, S, T, tot, le[M], lee[M], KK;
ll dis[M], deg[M], h[N], p[N];
bool in[M];
queue <ll> q;

void add(ll x, ll y, ll z, ll w) {
	e[++KK] = (node){z, w, y, le[x], KK + 1}; le[x] = KK;
	e[++KK] = (node){0, -w, x, le[y], KK - 1}; le[y] = KK;
}

bool SPFA() {
	for (ll i = 0; i <= tot; i++) {
		dis[i] = INF;
		in[i] = 0;
		deg[i] = -1;
		lee[i] = le[i];
	}
	while (!q.empty()) q.pop();
	
	q.push(S);
	dis[S] = 0;
	in[S] = 1;
	deg[S] = 0;
	while (!q.empty()) {
		ll now = q.front();
		q.pop();
		
		for (ll i = le[now]; i; i = e[i].nxt)
			if (e[i].x > 0 && dis[e[i].to] > dis[now] + e[i].w) {
				dis[e[i].to] = dis[now] + e[i].w;
				deg[e[i].to] = deg[now] + 1;
				if (!in[e[i].to]) {
					in[e[i].to] = 1;
					q.push(e[i].to);
				}
			}
		
		in[now] = 0;
	}
	
	if (dis[T] == dis[0]) return 0;
	return 1;
}

ll dfs(ll now, ll sum) {
	if (now == T) return sum;
	in[now] = 1;
	ll go = 0;
	for (ll &i = lee[now]; i; i = e[i].nxt)
		if (!in[e[i].to] && e[i].x > 0 && dis[e[i].to] == dis[now] + e[i].w && deg[e[i].to] == deg[now] + 1) {
			ll this_go = dfs(e[i].to, min(sum - go, e[i].x));
			if (this_go) {
				e[i].x -= this_go;
				e[e[i].op].x += this_go;
				go += this_go;
				if (go == sum) return go;
			}
		}
	if (go == sum) in[now] = 0;
	return go;
}

ll dinic_cost() {
	ll re = 0;
	while (SPFA()) {
		re += dis[T] * dfs(S, INF);
	}
	return re;
}

int main() {
	freopen("seq.in", "r", stdin);
	freopen("seq.out", "w", stdout);
	
	scanf("%lld %lld", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%lld", &h[i]);
	for (int i = 1; i <= n + 1; i++) p[i] = h[i] - h[i - 1];
	
	S = n + 2;
	T = n + 3;
	tot = T;
	
	for (int i = 1; i <= n + 1; i++) {
		if (i == 1 || i == n + 1) add(S, i, inf, 0);
			else if (p[i] > 0) add(S, i, p[i], 0);
				else if (p[i] < 0) add(i, T, -p[i], 0);
	}
	for (int i = 1; i <= m; i++) {
		char op = getchar(); while (op != '+' && op != '-') op = getchar();
		int l, c; scanf("%d %d", &l, &c); if (l == n) continue;
		for (int j = 1; j + l <= n + 1; j++) {
			if (op == '-') add(j, j + l, inf, c);
				else add(j + l, j, inf, c);
		}
	}
	
	ll ans = dinic_cost();
	for (int i = le[T]; i; i = e[i].nxt) {
		if (e[e[i].op].x) {
			printf("-1"); return 0;
		}
	}
	printf("%lld", ans);
	
	return 0;
}