【題目描述】
一個(gè)商人穿過(guò)一個(gè)N×N的正方形的網(wǎng)格，去參加一個(gè)非常重要的商務(wù)活動(dòng)。他要從網(wǎng)格的左上角進(jìn)，右下角出。每穿越中間1個(gè)小方格，都要花費(fèi)1個(gè)單位時(shí)間。商人必須在(2N-1)個(gè)單位時(shí)間穿越出去。而在經(jīng)過(guò)中間的每個(gè)小方格時(shí)，都需要繳納一定的費(fèi)用。

這個(gè)商人期望在規(guī)定時(shí)間內(nèi)用最少費(fèi)用穿越出去。請(qǐng)問(wèn)至少需要多少費(fèi)用？

注意：不能對(duì)角穿越各個(gè)小方格（即，只能向上下左右四個(gè)方向移動(dòng)且不能離開網(wǎng)格）。

【輸入】
第一行是一個(gè)整數(shù)，表示正方形的寬度N (1≤N<100)；

后面N行，每行N個(gè)不大于100的整數(shù)，為網(wǎng)格上每個(gè)小方格的費(fèi)用。

【輸出】
至少需要的費(fèi)用。

【輸入樣例】
5
1 4 6 8 10
2 5 7 15 17
6 8 9 18 20
10 11 12 19 21
20 23 25 29 33
【輸出樣例】
109
【提示】
樣例中，最小值為109=1+2+5+7+9+12+19+21+33。

分析

通過(guò)2N-1分析可以得到，商人不能走回頭路，這樣才能在n+n-1 =2n-1 個(gè)單位時(shí)間到達(dá)終點(diǎn)，所以和摘花生一樣；

但是這里最終答案是求最小值，所以把第0行、第0列初始化為較大值，不能按0來(lái)算；然后發(fā)點(diǎn)左上角需要特判；

#include<bits/stdc++.h>using namespace std;const int N = 110, INF = 1e9;int n; int a[N][N]; int f[N][N];int main() {cin >> n;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {cin >> a[i][j];}}//由于求最小，那就需要把第0行、第0列初始化為較大值for (int i = 1; i <= n; ++i) {f[i][0] = INF;f[0][i] = INF;}for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {//出發(fā)點(diǎn)左上角特判if (i == 1 && j == 1)f[i][j] = a[i][j];elsef[i][j] = min(f[i - 1][j] + a[i][j], f[i][j - 1] + a[i][j]);}}cout << f[n][n];return 0; }

總結(jié)

以上是生活随笔為你收集整理的1287：最低通行费——数字三角形模型的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。