#15193: 動態規劃(DP)


2qbingxuan (程式初學者)

學校 : 臺北市立建國高級中學
編號 : 58274
來源 : [114.32.125.176]
最後登入時間 :
2024-04-01 20:23:17
d378. 最小路徑 | From: [210.71.78.241] | 發表日期 : 2018-09-18 15:07

#include <bits/stdc++.h>
#define MAX_S 101

using namespace std;

int main(){
    uint16_t n, m, ct = 1;
    while(cin >> n >> m){
        uint32_t g[MAX_S + 1][MAX_S + 1] = {};
        uint32_t cost[MAX_S + 1][MAX_S + 1] = {};
        for(int i = 0;i < n;i++)
            for(int j = 0;j < m;j++)
                cin >> g[i][j],cost[i][j] = (i || j) * min(i ? cost[i - 1][j] : UINT_MAX,j ? cost[i][j - 1] : UINT_MAX) + g[i][j];
                cout << "Case #" << ct++ << " :\n" << cost[n - 1][m - 1] << endl;
    }
    return 0;
}

/*

由於地圖由左上填至右下(單方向)

因此直接使用DP

到達每格所需的最小體力 = min(到達左方一格所需最小體力 , 到達上方一格最小體力) + 此格所需體力

*/

 
ZeroJudge Forum