【题解】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 |
|