【题解】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 |
|
看不懂的标程
1 |
|