【题解】EOJ - 卡车运输 (kamion)

题目

http://acm.ecnu.edu.cn/problem/3437/

题意

有点复杂,请自行读题。

题解

  • $f[i][j][k]$ 从 $i$ 到 $j$ 走 $k$ 步且始末为空,且全程不空的方案数 (由装货,g,卸货组成)

    $$f[i][j][k]=\displaystyle \sum_{i \stackrel{type 1(X)}{\longrightarrow}a} \sum_{b \stackrel{type 2(x)}{\longrightarrow} j}g[a][b][k-2]$$

  • $empty[i][j][k]$ 从 $i$ 到 $j$ 走 $k$ 步且全程为空方案数 (由 empty 和 第三种路组成)

    $$empty[i][j][k]=\displaystyle \sum_{t \stackrel{type 3}{\longrightarrow}j}empty[i][t][k-1]$$

  • $g[i][j][k]$ 从 $i$ 到 $j$ 走 $k$ 步且始末为空的方案数 (由 g 和 gg 组成)

    $$g[i][j][k]=\displaystyle \sum_{t=1}^n \sum_{k’=0}^{k} g[i][t][k’] \times gg[t][j][k-k’]$$

  • $gg[i][j][k]$ (由 f 和 empty 组成)用于追加在 g 尾部形成新的 g。

    $$gg[i][j][k]=\displaystyle \sum_{t=1}^n \sum_{k’=0}^{k} f[i][t][k’] \times empty[t][j][k-k’]+empty[i][j][k]$$

  • $h[i][j][k]​$ 从 $i​$ 到 $j​$ 走 $k​$ 步且一开始为空的方案数(由 1、3 两种路以及 f 组成)

    $$h[i][j][k]=\displaystyle \sum_{t=1}^n \sum_{k’=0}^{k} h[i][t][k’] \times f[t][j][k-k’] + \sum_{t \stackrel{type 1/3}{\longrightarrow} j}h[i][t][k-1]$$

  • 由于只要求不超过 k 步,那么最后的答案为 $\sum_{k=0}^K h[1][n][k]$,复杂度 $O(n^5)​$,由于我用的是邻接矩阵而非邻接表,所以常数会大一些。

  • 搞了那么多状态转移方程,到底有什么必要呢?很遗憾,很可能是做复杂了。

  • 这样做为什么是对的呢?由于转移的时候是枚举 中转站,所以必须保证对于特定的一种方案,只可能在某个特定的点作为中转站时被累加。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args<< " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int maxn = 50 + 5;
const int MOD = 10000 + 7;
int n, m, K;
int G[maxn][maxn];
int f[maxn][maxn][maxn], empty[maxn][maxn][maxn], g[maxn][maxn][maxn], h[maxn][maxn][maxn];
int gg[maxn][maxn][maxn];

inline void up(int& a, int b) { (a += b) %= MOD; }

int main() {
#ifdef zerol
freopen("in", "r", stdin);
#endif
cin >> n >> m >> K;
int u, v;
char s[100];
FOR (_, 0, m) {
scanf("%d%d", &u, &v);
--u; --v;
gets(s);
if (strlen(s)) G[u][v] = s[1];
else G[u][v] = 1;
}
FOR (i, 0, n) h[i][i][0] = g[i][i][0] = empty[i][i][0] = 1;
FOR (k, 1, K + 1)
FOR (i, 0, n)
FOR (j, 0, n) {
if (k >= 2) FOR (a, 0, n) FOR (b, 0, n)
if (isupper(G[i][a]) && tolower(G[i][a]) == G[b][j])
up(f[i][j][k], g[a][b][k - 2]);
FOR (t, 0, n)
up(empty[i][j][k], empty[i][t][k - 1] * (G[t][j] == 1));
FOR (t, 0, n)
FOR (kk, 0, k + 1)
up(gg[i][j][k], f[i][t][kk] * empty[t][j][k - kk]);
FOR (t, 0, n)
FOR (kk, 0, k + 1)
up(g[i][j][k], g[i][t][kk] * gg[t][j][k - kk]);
up(g[i][j][k], empty[i][j][k]);

FOR (t, 0, n)
FOR (kk, 0, k + 1)
up(h[i][j][k], h[i][t][kk] * f[t][j][k - kk]);

FOR (t, 0, n)
up(h[i][j][k], (G[t][j] == 1 || isupper(G[t][j])) * h[i][t][k - 1]);
}

int ans = 0;
FOR (k, 0, K + 1) up(ans, h[0][n - 1][k]);

cout << ans << endl;
}

看不懂的标程

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
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <vector>

using namespace std;

#define MAXN 50
#define MAXK 50
#define MAXT 26
#define MOD 10007
#define ADD(a, b) a = (a + b) % MOD
#define FOR_EACH(it, cont) \
for(vector<par>::iterator it = cont.begin(); it != cont.end(); ++it)

int N, E, K;
typedef pair<int, int> par;
vector<par> road[MAXN];
vector<par> load[MAXN][MAXT];
vector<par> drop[MAXN][MAXT];
vector<par> road_plus_load[MAXN];

int dp[MAXK+1][MAXN][MAXN][2];
int helper[MAXK+1][MAXN][MAXN];

int main(void) {
char line[128];
scanf("%d%d%d", &N, &E, &K); gets(line);
for (int i = 0; i < E; ++i) {
int A, B;
char type;
gets(line);
int scanned = sscanf(line, "%d %d %c", &A, &B, &type); --A; --B;
if (scanned == 2) {
road[A].push_back(par(A, B));
road_plus_load[A].push_back(par(A, B));
} else if (isupper(type)) {
load[A][type - 'A'].push_back(par(A, B));
road_plus_load[A].push_back(par(A, B));
} else {
drop[B][type - 'a'].push_back(par(A, B));
}
}

for (int i = 0; i < N; ++i)
for (int flag = 0; flag < 2; ++flag)
dp[0][i][i][flag] = 1;

int ret = 0;
for (int k = 1; k <= K; ++k) {
if (k >= 2)
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
for (int t = 0; t < MAXT; ++t)
FOR_EACH(it, load[i][t])
FOR_EACH(jt, drop[j][t])
ADD(helper[k][i][j], dp[k-2][it->second][jt->first][0]);

for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
for (int flag = 0; flag < 2; ++flag) {
vector<par> &roads = flag ? road_plus_load[i] : road[i];
FOR_EACH(it, roads)
ADD(dp[k][i][j][flag], dp[k-1][it->second][j][flag]);

for (int t = 2; t <= k; ++t)
for (int x = 0; x < N; ++x)
ADD(dp[k][i][j][flag], helper[t][i][x] * dp[k-t][x][j][flag]);
}

ADD(ret, dp[k][0][N-1][1]);
}
printf("%d\n", ret);

return 0;
}