题解 / LibreOJ
8 minutes read (About 1252 words)

题解-LibreOJ-6032「雅礼集训 2017 Day2」水箱

题目链接

题目概括重金征集中~

比较毒瘤的一道题。

注意到每个条件只有“有水”限制和“没水”限制。问题在于如何统计最多能满足多少条件。假定所有的“没水”条件都能满足，在 DP 中如果在“没水”限制的格子中填入了水，则对答案的贡献减一；如果在“有水”限制的格子中填入了水，则对答案的贡献加一。

根据以上方法，可以定义状态：$f[i][j]$ 表示在从左往右第 $i$ 个格子中，高度为 $j$ 的地方有水时对答案产生的最大贡献。注意：此时假定第 $i$ 个格子的右侧挡板为无限高。

显然，如果 $j$ 小于等于其左侧挡板的高度，上一格的水的高度可以为 $1-h[i]$ 的任意值；如果 $j$ 大于其左侧挡板的高度，那么上一格的水的高度必须同样为 $j$。

状态转移方程如下：
$$
f[i][j]=
\begin{cases}
\sum_{k=1}^{j} w[i][k]+\max_{k=1}^{h[i]}\lbrace f[i-1][k]\rbrace,\ j\le h[i]
\
\sum_{k-1}^{j} w[i][k]+f[i-1][j],\ j>h[i]

\end{cases}
$$
不难发现可以使用滚动数组优化空间；并且注意到，每个新的 $f[i][j]$ 要么是被修改成某个值，要么是在原来的基础上加上了某些东西。

在本题中，每个格子中限制条件的分布是相对稀疏的。那么，在同一格子的不同高度处，只要其对答案的贡献前缀和相等，则可以作为区间进行快速处理。

具体来说，可以使用线段树维护 $f[1]-f[L]$，并在其中用滚动数组的操作进行状态转移。这棵线段树需要支持区间修改（替换），区间修改（增加），区间查询最大值。

注意需要对高度进行离散化处理。

代码如下：

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#include <bits/stdc++.h>
#define lson(u) node[u].l
#define rson(u) node[u].r
#define val(u) node[u].val
#define tag1(u) node[u].tag1
#define tag2(u) node[u].tag2
#define id(x) (lower_bound(b + 1, b + L + 1, x) - b)
#define rid(x) b[x]
using namespace std;

const int MAXN = 400005;
const int inf = 0x3f3f3f3f;

struct Node {
    int l, r, val, tag1, tag2;
    // val: max
    // tag1: replace
    // tag2: add
}node[MAXN * 3];
int cnt;

struct Limit {
    int x, y, k;
}limit[MAXN];

int T, N, M;
int R, L;

int b[MAXN], h[MAXN];

inline void build(int& u, int l, int r) {
    u = ++cnt;
    tag1(u) = -inf;
    tag2(u) = 0;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(lson(u), l, mid);
    build(rson(u), mid + 1, r);
}

inline void pushdown(int u) {
    if (tag1(u) != -inf) {
        val(lson(u)) = val(rson(u)) = tag1(u);
        tag1(lson(u)) = tag1(rson(u)) = tag1(u);
        tag2(lson(u)) = tag2(rson(u)) = 0;
        tag1(u) = -inf;
    }
    if (tag2(u) != 0) {
        val(lson(u)) += tag2(u);
        val(rson(u)) += tag2(u);
        tag2(lson(u)) += tag2(u);
        tag2(rson(u)) += tag2(u);
        tag2(u) = 0;
    }
}

inline void pushup(int u) {
    val(u) = max(val(lson(u)), val(rson(u)));
}

inline void modify_replace(int u, int l, int r, int ql, int qr, int val) {
    if (ql > qr) return;
    pushdown(u);
    if (ql <= l && r <= qr) {
        val(u) = val;
        tag1(u) = val;
        return;
    }
    int mid = (l + r) >> 1;
    if (ql <= mid) modify_replace(lson(u), l, mid, ql, qr, val);
    if (mid < qr) modify_replace(rson(u), mid + 1, r, ql, qr, val);
    pushup(u);
}

inline void modify_add(int u, int l, int r, int ql, int qr, int val) {
    if (ql > qr) return;
    pushdown(u);
    if (ql <= l && r <= qr) {
        val(u) += val;
        tag2(u) = val;
        return;
    }
    int mid = (l + r) >> 1;
    if (ql <= mid) modify_add(lson(u), l, mid, ql, qr, val);
    if (mid < qr) modify_add(rson(u), mid + 1, r, ql, qr, val);
    pushup(u);
}

inline int query_max(int u, int l, int r, int ql, int qr) {
    pushdown(u);
    if (ql <= l && r <= qr) {
        return val(u);
    }
    int mid = (l + r) >> 1, ret = -inf;
    if (ql <= mid) ret = max(ret, query_max(lson(u), l, mid, ql, qr));
    if (mid < qr) ret = max(ret, query_max(rson(u), mid + 1, r, ql, qr));
    return ret;
}

inline bool cmp(Limit a, Limit b) {
    if (a.x != b.x) return a.x < b.x;
    if (a.y != b.y) return a.y < b.y;
    return a.k < b.k;
}

int main() {
    scanf("%d", &T);
    while (T--) {
        memset(node, 0, sizeof(node));
        cnt = 0, L = 0, R = 0;
        int ans1 = 0;
        scanf("%d%d", &N, &M);
        for (register int i = 2; i <= N; ++i) {
            scanf("%d", &h[i]);
            b[++L] = h[i];
        }
        for (register int i = 1; i <= M; ++i) {
            scanf("%d%d%d", &limit[i].x, &limit[i].y, &limit[i].k);
            limit[i].y++;
            if (limit[i].k == 0) limit[i].k = -1, ans1++;
            b[++L] = limit[i].y;
            b[++L] = limit[i].y - 1;
        }
        sort(b + 1, b + L + 1);
        L = unique(b + 1, b + L + 1) - b - 1;
        h[1] = L;
        build(R, 1, L);
        for (register int i = 2; i <= N; ++i)
            h[i] = id(h[i]);
        for (register int i = 1; i <= M; ++i)
            limit[i].y = id(limit[i].y);
        sort(limit + 1, limit + M + 1, cmp);
        int cur = 1;
        for (register int i = 1; i <= N; ++i) {
            int height = 1, s = 0;
            int tmp = query_max(R, 1, L, 1, h[i]);
            while (limit[cur].x == i && limit[cur].y <= h[i]) {
                int w = limit[cur].k;
                while (limit[cur].x == limit[cur + 1].x && limit[cur].y == limit[cur + 1].y) {
                    w += limit[++cur].k;
                }
                modify_replace(R, 1, L, height, id(rid(limit[cur].y) - 1), s + tmp);
                height = limit[cur].y;
                s += w;
                cur++;
            }
            if (height <= h[i])
                modify_replace(R, 1, L, height, h[i], s + tmp);
            height = h[i] + 1;
            while (limit[cur].x == i) {
                int w = limit[cur].k;
                while (limit[cur].x == limit[cur + 1].x && limit[cur].y == limit[cur + 1].y) {
                    w += limit[++cur].k;
                }
                modify_add(R, 1, L, height, id(rid(limit[cur].y) - 1), s);
                height = limit[cur].y;
                s += w;
                cur++;
            }
            if (height <= L)
                modify_add(R, 1, L, height, L, s);
        }
        printf("%d\n", ans1 + query_max(R, 1, L, 1, L));
    }
    return 0;
}
# 动态规划, 离散化, 线段树
解题报告-NOIP2017提高组初赛
题解-luogu-p3960列队

Comments

Follow

一言（ヒトコト）


    2333



Recent

Categories

Tag Cloud

0/1分数规划 2-SAT FFT/NTT KMP Pólya计数 ST算法 bitset dfs序 python set 主席树 乘法逆元 二分图 二分图匹配 二分答案 二叉堆 二维偏序 倍增 分块 前缀和 动态点分治 动态规划 单调队列 博弈论 卡特兰数 可持久化trie 后缀自动机 启发式合并 哈希(hash) 堆 复杂度分析 多项式 字符串 容斥原理 差分 差分约束系统 平衡树 异或 强连通分量 排序 搜索 数学 数学期望 数据结构 数论 最小割 最短路 最短路树 最近公共祖先 构造 栈 树上前缀和 树上差分 树套树 树形dp 树状数组 树链剖分 概率 欧拉函数 欧拉路 点分治 状态压缩 生成函数 生成树 矩阵 离散化 素数 线性基 线段树 组合数 组合计数 网络流 群论 背包 虚树 行列式 计数dp 计算几何 贪心 费用流 逆元 高斯消元
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×