AHSDFZ 模拟赛怪题

Description

给出一个长度为o的整数序列h_j ，现在要通过一些操作将这个序列修改

为单调不降序列，即h_j ≤ h_j+1 。

可以用的操作有n种，第j种操作可以通过支付d_j 的代价将一段长度恰

为m_j的连续子序列+1或−1（由对应的操作符确定是+1还是−1，具体参考

输入格式）。

不限制每种操作的使用次数，序列中的h_j 可以被改为任意整数（可以

是负数），求最小代价，无解输出−1。

Input

从文件 seq.in 中读入数据。

第一行，两个整数o,n。

第二行，o个整数h_j 。

接下来?行，每行格式为p_j ,m_j,d_j 空格隔开，其中p_j 为一个字符，表示

这种操作是+1还是−1。

Output

输出到文件 seq.out 中。

输出一行一个整数表示最小代价，若无解输出-1。

Sample Input

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
10 10
23 1 8 14 2 3 15 50 53 53
+ 4 6
- 1 10
+ 2 4
+ 4 2
- 3 5
+ 1 2
+ 3 2
+ 5 7
- 1 6
+ 4 5

Sample Output

1
96

Constraint

对于20%的数据，o,n ≤ 5，h_j ≤ 10，d_j ≤ 3。

对于另20%的数据，m_j = 1，h_j ≤ 500。

对于100%的数据，o,n ≤ 200，m_j ≤ o，1 ≤ h_j ,d_j ≤ 10^6 。

Solution

最小费用最大流。

考场上这个题毫无思路，思想僵化的我只能想到差分。

首先差分数组，发现我们如果要达到题目中的条件，需要这个差分后的数组的值都大于0。

于是我们就变成了另一个问题：给你一个序列，可以给一个位置i上的数字+1或者-1，然后给i+len位置上的数字-1或+1，并付出cost的代价。

我们不妨把+1/-1的操作想象为续命，一个正数可以-1，并且给一个负数+1s

于是对于一个操作 type len cost，根据type的不同，将所有的i向i+len连费用cost，流量inf的边。

S向正数x流x的流量，费用0，负数x向T流-x的流量，费用0。

这样我们就完成了建模。

但是这样会WA，因为一个数字可以减为负数。

于是我们在差分后的序列首和序列尾插入两个inf就好了，表明0和n+1的位置可以不停地给别的元素续。

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long LL;
const LL LINF = 1000000007;
int getint() {
    int r = 0, k = 1; char c = getchar();
    for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
    for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
    return r * k;
}
struct edge_type {
    int to, next;
    LL r;
    LL c;
} edge[100005];
int S, T, pre[100005], cnte = 1, h[100005], tot;
LL a[100005];
LL dis[100005];
bool vis[100005];
queue<int> Q;
void ins(int u, int v, LL f, LL c) {
    edge[++cnte].to = v;
    edge[cnte].next = h[u];
    h[u] = cnte;
    edge[cnte].r = f;
    edge[cnte].c = c;
    edge[++cnte].to = u;
    edge[cnte].next = h[v];
    h[v] = cnte;
    edge[cnte].r = 0;
    edge[cnte].c = -c;
}
bool SPFA(int &flow, LL &cost) {
    for (int i = 1; i <= tot; ++i) dis[i] = LINF, vis[i] = false;
    pre[S] = 0; dis[S] = 0; vis[S] = true; a[S] = LINF;
    Q.push(S);
    int now;
    while (!Q.empty()) {
        now = Q.front(); Q.pop();
        vis[now] = false;
        for (int i = h[now]; i; i = edge[i].next) {
            if (!edge[i].r) continue;
            if (dis[edge[i].to] > dis[now] + edge[i].c) {
                dis[edge[i].to] = dis[now] + edge[i].c;
                a[edge[i].to] = min(a[now], edge[i].r);
                pre[edge[i].to] = i;
                if (!vis[edge[i].to]) {
                    vis[edge[i].to] = true;
                    Q.push(edge[i].to);
                }
            }
        }
    }
    if (dis[T] == LINF) return false;
    flow += a[T];
    cost += a[T] * dis[T];
    for (now = T; now != S; now = edge[pre[now]^1].to) {
        edge[pre[now]].r -= a[T];
        edge[pre[now]^1].r += a[T];
    }
    return true;
}
int n, m, id[100005], tmp;
int main() {
    n = getint();
    m = getint();
    S = ++tot; T = ++tot;
    id[0] = ++tot;
    for (int i = 1; i <= n; ++i) {
        a[i] = getint();
        id[i] = ++tot;
    }
    for (int i = 1; i < n; ++i) {
        int d = a[i+1] - a[i];
        if (d < 0) { tmp -= d; ins(id[i], T, -d, 0); }
        else ins(S, id[i], d, 0);
    }
    ins(S, id[0], LINF, 0);
    ins(S, id[n], LINF, 0);
    char str[3];
    int l, c;
    while (m--) {
        scanf("%s", str);
        l = getint(); c = getint();
        if (str[0] == '-')
            for (int i = 0; i + l <= n; ++i)
                ins(id[i], id[i+l], LINF, c);
        else
            for (int i = 0; i + l <= n; ++i)
                ins(id[i+l], id[i], LINF, c);
    }
    int flow = 0;
    LL cost = 0;
    while (SPFA(flow, cost));
    if (flow != tmp) puts("-1");
    else printf("%lld", cost);
}