题目：UVA - 590Always on the run（递推）

题目大意：有一个小偷现在在计划着逃跑的路线，但是又想省机票费。他刚开始在城市1，必须K天都在这N个城市里跑来跑去，最后一天达到城市N，问怎样计划路线的得到最少的费用。

解题思路：一开始题目意思就理解有些问题。

dp【k】【i】：代表在第k天小偷从某一个城市（除了i）坐飞机飞到城市i（到达城市i也是在这一天）。第k天的话，就看这一天坐哪个航班，加上之前的费用是最小的，就选这个方案。然后k+ 1天就又是由第k天推出来的。

状态转移方程：dp【k】【i】 = Min （dp【k - 1】【j】（i ！= j) + v[j][i][k]).

代码：

#include 
  
   
#include 
   
     const int N = 15; const int M = 35; const int maxn = 1005; const int INF = 0x3f3f3f3f; int n, k; int t[N][N]; int v[N][N][M]; int dp[maxn][N]; int Min (const int a, const int b) { return a < b? a: b; } int main () { int cas = 0; while (scanf ("%d%d", &n, &k), n || k) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i == j) continue; scanf ("%d", &t[i][j]); for (int d = 0; d < t[i][j]; d++) { scanf ("%d", &v[i][j][d]); if (v[i][j][d] == 0) v[i][j][d] = INF; } } } for (int i = 1; i <= k; i++) for (int j = 1; j <= n; j++) dp[i][j] = INF; for (int i = 2; i <= n; i++) dp[1][i] = v[1][i][0]; for (int d = 2; d <= k; d++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { if (i != j && dp[d - 1][j] != INF) dp[d][i] = Min (dp[d][i], dp[d - 1][j] + v[j][i][(d - 1) % t[j][i]]); } //printf ("%lld\n", INF); printf ("Scenario #%d\n", ++cas); if (dp[k][n] != INF) printf ("The best flight costs %d.\n\n", dp[k][n]); else printf ("No flight possible.\n\n"); } return 0; }