http://codeforces.com/contest/1483

C. Skyline Photo

 

题意：给定 nn 栋楼，每栋有高度 hih_i 且互不相同，还有魅力值 aia_i，要求分割成几块，每块的魅力值等于该块内最矮的楼的魅力值。要求最大化魅力值之和。

dp+线段树+单调栈

dp[i]dp[i] 表示前 ii 栋楼魅力值之和最大值。

枚举 ii 所在块长度，则转移显然 dp[i]=max⁡j=1i(dp[j−1]+a[k])dp[i]=\max\limits_{j=1}^{i}(dp[j-1]+a[k])，其中 kk 为 [j⋯i][j\cdots i] 的中最矮的楼。

那么可以发现对于一些 jj，他们对应的 kk 可能是相同的，这样就可以放在一起求最大值。

维护递增的单调栈，则满足 stack[top]stack[top] 是 [stack[top]⋯i][stack[top]\cdots i] 中最矮的。

线段树维护 dp[j]+a[k]dp[j]+a[k]，其中 kk 为当前遍历到第 ii 栋楼时，jj 与 ii 中间最矮的楼。

对于 ii，加入单调栈后它与栈中前一个位置的楼中间所有的楼 jj，对应的 kk 都是 ii，所以更新线段树。从单调栈中弹出时更新回去。求出 dp[i]dp[i] 后更新到线段树上。

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
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 5e5 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
int n;
int h[N];
ll a[N], dp[N];
int st[N], tp;
#define mid ((l+r)>>1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
ll tr[N << 2], laz[N << 2];
void up(int rt) {
	tr[rt] = max(tr[rt << 1], tr[rt << 1 | 1]);
}
void down(int rt) {
	ll& x = laz[rt];
	if (x) {
		tr[rt << 1] += x;
		tr[rt << 1 | 1] += x;
		laz[rt << 1] += x;
		laz[rt << 1 | 1] += x;
		x = 0;
	}
}
void build(int l, int r, int rt) {
	if (l == r) {
		if (l == 0)tr[rt] = 0;
		else tr[rt] = -inf;
		return;
	}
	build(lson);
	build(rson);
	up(rt);
}
void cg(int q, ll x, int l, int r, int rt) {
	if (l == r) {
		tr[rt] = x;
		return;
	}
	down(rt);
	if (q <= mid)cg(q, x, lson);
	else cg(q, x, rson);
	up(rt);
}
void upd(int ql, int qr, ll x, int l, int r, int rt) {
	if (ql <= l && qr >= r) {
		tr[rt] += x;
		laz[rt] += x;
		return;
	}
	down(rt);
	if (ql <= mid)upd(ql, qr, x, lson);
	if (qr > mid)upd(ql, qr, x, rson);
	up(rt);
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%d", &h[i]);
	for (int i = 1; i <= n; i++)scanf("%lld", &a[i]);
	build(0, n, 1);
	st[tp++] = 0;
	for (int i = 1; i <= n; i++) {
		while (tp&&h[st[tp]] > h[i]) {
			upd(st[tp - 1], st[tp] - 1, -a[st[tp]], 0, n, 1);
			tp--;
		}
		st[++tp] = i;
		upd(st[tp - 1], st[tp] - 1, a[i], 0, n, 1);
		dp[i] = tr[1];
		cg(i, dp[i], 0, n, 1);
	}
	printf("%lld\n", dp[n]);
	return 0;
}

 

D. Useful Edges

 

题意：给定一张带边权无向图 2≤n≤600,0≤m≤n(n−1)22\leq n\leq 600,0\leq m\leq \frac{n(n-1)}2，给定 q,1≤q≤n(n−1)2q,1\leq q\leq \frac{n(n-1)}2 个三元组 (u,v,l)(u,v,l)。定义一条边为有用边当且仅当存在一个三元组 (u,v,l)(u,v,l) 满足：存在从 uu 到 vv 的路径（可以不是简单路径），且该路径经过这条边，且该路径长度不超过 ll。问有几条有用边。

Floyd最短路+枚举

说是最短路，但我感觉难点在枚举方法上。

对于一条边 (u,v)(u,v)，它有用等价于 存在一个三元组 (i,j,l[i][j])(i,j,l[i][j])，满足 l[i][j]≥dist[u][j]+dist[v][i]+w[u][v]l[i][j]\ge dist[u][j]+dist[v][i]+w[u][v]。

枚举 边的一个端点 uu，以及三元组的一个端点 ii，再枚举边的另一个端点 vv，把上一行的式子移项，这样判断 (u,v)(u,v) 是否有用就变成判断是否存在 jj，使得 l[i][j]−dist[u][j]≥dist[v][i]+w[u][v]l[i][j]-dist[u][j]\ge dist[v][i]+w[u][v]，可以看到左边与 vv 无关，右边与 jj 无关，所以就可以分开算了，因此就变成判断 dist[v][i]+w[u][v]≤max⁡j=1n(l[i][j]−dist[u][j])dist[v][i]+w[u][v]\le\max\limits_{j=1}^n (l[i][j]-dist[u][j])。故只需要先枚举 jj 计算出 max⁡j=1n(l[i][j]−dist[u][j])\max\limits_{j=1}^n (l[i][j]-dist[u][j])，再枚举 vv 判断即可。

复杂度 O(n3)O(n^3)。

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
#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 5e5 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
int n, m, q;
ll d[1010][1010], e[1010][1010], l[1010][1010];

int main() {
	scanf("%d%d", &n, &m);
	memset(e, -1, sizeof(e));
	memset(d, 0x3f, sizeof(d));
	for (int i = 1; i <= n; i++)d[i][i] = 0;
	for (int i = 1; i <= m; i++) {
		int u, v; ll w;
		scanf("%d%d%lld", &u, &v, &w);
		e[v][u] = e[u][v] = d[u][v] = d[v][u] = w;
	}
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
	scanf("%d", &q);
	while (q--) {
		int u, v; ll w;
		scanf("%d%d%lld", &u, &v, &w);
		l[u][v] = l[v][u] = w;
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		for (int u = 1; u <= n; u++) {
			ll mx = -inf;
			for (int j = 1; j <= n; j++) {
				if (!l[i][j])continue;
				mx = max(mx, l[i][j] - d[u][j]);
			}
			for (int v = 1; v <= n; v++) {
				if (e[u][v] != -1 && d[i][v] + e[u][v] <= mx) {
					ans++;
					e[v][u] = e[u][v] = -1;
				}
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}