UVa10350 - Liftless EME(DP、Directed Acyclic Graph)

題目大意

EME 大樓有非常多層樓，每一個學生要透過樓梯爬上去，現在學校舉行一場比賽，看學生們從一樓走到頂樓，誰最快，想請問最快必須花幾分鐘

題目給的格式如下，有 n,m，其中 ```for(int k = 1; k <= m; k++)，其中 n 表示第幾層樓走到第 n+1 個樓的第 k 個樓梯要花幾分鐘，且每爬一層樓需要花兩分鐘。

題目格式讓我非常看不懂
題目連結

重點觀念

• 演算法知識 - Directed Acyclic Graphby 大衛的筆記

分析

• 由於起點都是在一樓且可以透過任意一個樓梯開始行走，因此起點並不是都在同個位置，你可以考慮起點在一樓第二個樓梯…
• 符合 DAG 特性，不會有環，不斷向前進，且起點不只一個，因此使用 DP
• dp公式 dp[下一層樓][k號樓梯] = min(dp[這層樓][k號樓梯] + cost[這層樓][到下一樓][經過 k 號樓梯],dp[下一層樓][k號樓梯] )

參考連結

UVa10350 - Liftless EME by morris

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define int long long
#define MAXN 150
#define INF 0x3f3f3f
#define LOCAL
using namespace std;
int n, m;
int cost[MAXN][20][20];
int dp[MAXN][20];
string s;

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL

    while(cin >> s){
        cin >> n >> m;
        for(int i = 1; i < n; i++){
            for(int j = 1; j <= m; j++){
                for(int k = 1; k <= m; k++){
                    cin >> cost[i][j][k]; //cost[這層樓][到下一樓][經過 k 號樓梯]
                }
            }
        }

        for(int i = 0; i < MAXN; i++){ //一開始設為無限大，因為題目要求最小
            for(int j = 0; j < 20; j++){
                dp[i][j] = INF;
            }
        }
        for(int i = 0; i < 20; i++) dp[1][i] = 0; //一樓全部都是起點，設為0

        for(int i = 1; i <= n; i++){ //分析 3
            for(int j = 1; j <= m; j++){
                for(int k = 1; k <= m; k++){
                    dp[i+1][k] = min(dp[i][j] + cost[i][j][k] ,dp[i+1][k]);
                }
            }
        }

        int ans = INF; 
        for(int i = 1; i <= m; i++) ans = min(dp[n][i], ans);//看誰最小
        cout << s << "\n";
        cout << (ans + 2*n-2) << "\n"; //加上爬樓時需要的時間
    }
    return 0;
}