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