codechef-TBGRAPH-题解

发表于

Graph on a Table

题意

有一张 $ n \times m $ 的网格图，每次可以从 $ (x_0, y_0) $ 跳到 $ (x_1, y_1) $ 当且仅当 $ x_0 < x_1 $ 且 $ y_0 < y_1 $ ，同时这两个点都要在同一个给出的矩形中，求最多可以经过多少个网格并求出方案数对 $ 10^9 + 7 $ 取模。

做法

由于要求的是最长路经，所以对于路径相邻的两个位置 $ (x_i, y_i) $ 和 $ (x_{i + 1}, y_{i + 1}) $ 满足 $ x_i + 1 = x_{i + 1} $ 或 $ y_i + 1 = y_{i + 1} $ 。
考虑DP，预处理出每个点可以从那些地方转移( $ Left[i][j] $ 和 $ Up[i][j] $ 分别维护这个点可以转移的最左和最上方的位置 )。
然后单调队列优化DP即可。 

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
#include <bits/stdc++.h>
#define mp make_pair
#define fst first
#define snd second
#define rep(i, a, b) for(int i = (a), i##ed = (b); i <= i##ed; i++)
#define per(i, a, b) for(int i = (a), i##ed = (b); i >= i##ed; i--)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1e9 + 7;
const int N = 2010, M = 500010;

inline void file() {
	freopen("roche.in", "r", stdin);
	freopen("roche.out", "w", stdout);
}
inline int Max(int x, int y) { return x > y ? x : y; }
inline int Min(int x, int y) { return x < y ? x : y; }
void gi(int &x) {
	x= 0; register char c = getchar();
	for(; c < '0' || c > '9'; c = getchar());
	for(; c >= '0' && c <= '9';)
		x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
}

int T, n, m, q;
struct P {
	int x, y, xx, yy;
	inline bool operator<(const P &yy)const { return x < yy.x; }
}; P a[M];
int up[N][N], lt[N][N];
struct Node {
	int len, s; Node(int X = 0, int Y = 0) : len(X), s(Y) {}
	inline bool operator<(const Node &yy)const { return len < yy.len; }
}; Node ans, f[N][N];
struct Queue {
	Node a[N]; int f, e, s[N], id[N];
	void init(int x) { f = 1, e = 0; rep(i, 1, x) s[i] = 0; }
	void push(int x, Node w) {
		for(; f <= e && a[e] < w;)
			s[a[e].len] = (s[a[e].len] - a[e].s + mod) % mod, --e;
		s[w.len] = (s[w.len] + w.s) % mod, a[++e] = w, id[e] = x;
	}
	Node ask(int x) {
		for(; f <= e && id[f] < x;)
			s[a[f].len] = (s[a[f].len] - a[f].s + mod) % mod, ++f;
		return Node(a[f].len + 1, s[a[f].len]);
	}
}; Queue Up[N], Lt[N];

inline Node operator+(Node x, Node y) {
	if(x.len ^ y.len) return x.len > y.len ? x : y;
	return Node(x.len, (x.s + y.s) % mod);
}
void get_up_lt() {
	rep(i, 1, n) rep(j, 1, m) up[i][j] = lt[i][j] = 0x3f3f3f3f;
	rep(i, 1, q) {
		rep(j, a[i].x + 1, a[i].xx)
			lt[j][a[i].yy] = Min(a[i].y, lt[j][a[i].yy]);
		rep(j, a[i].y + 1, a[i].yy)
			up[a[i].xx][j] = Min(a[i].x, up[a[i].xx][j]);
	}
	per(i, n, 1) per(j, m, 1) {
			if(j < m) lt[i][j] = Min(lt[i][j + 1], lt[i][j]);
			if(i < n) up[i][j] = Min(up[i + 1][j], up[i][j]);
			if(lt[i][j] >= j) lt[i][j] = 0x3f3f3f3f;
			if(up[i][j] >= i) up[i][j] = 0x3f3f3f3f;
		}
}
void solve() {
	gi(n), gi(m), gi(q);
	rep(i, 1, q) gi(a[i].x), gi(a[i].y), gi(a[i].xx), gi(a[i].yy);
	get_up_lt();
	rep(i, 1, n) Lt[i].init(m); rep(i, 1, m) Up[i].init(n);
	rep(i, 1, n) rep(j, 1, m) f[i][j] = Node(1, 1);
	rep(i, 1, n) rep(j, 1, m) {
		Lt[i].push(j, f[i][j]), Up[j].push(i, f[i][j]);
		if(lt[i + 1][j + 1] != 0x3f3f3f3f)
			f[i + 1][j + 1] = f[i + 1][j + 1] + Lt[i].ask(lt[i + 1][j + 1]);
		if(up[i + 1][j + 1] != 0x3f3f3f3f)
			f[i + 1][j + 1] = f[i + 1][j + 1] + Up[j].ask(up[i + 1][j + 1]);
		if(up[i + 1][j + 1] != 0x3f3f3f3f && lt[i + 1][j + 1] != 0x3f3f3f3f &&
			f[i][j].len + 1 == f[i + 1][j + 1].len)
			f[i + 1][j + 1].s = (f[i + 1][j + 1].s - f[i][j].s + mod) % mod;
	}
	ans = Node(0, 0);
	rep(i, 1, n) rep(j, 1, m) ans = ans + f[i][j];
	printf("%d %d\n", ans.len, ans.s);
}
int main() {
//	file();
	for(scanf("%d", &T); T; --T) solve();
	return 0;
}