題目鏈接
題目描述
一個商人穿過一個 N×N 的正方形的網格，去參加一個非常重要的商務活動，
他要從網格的左上角進，右下角出，
每穿越中間 1 個小方格，都要花費 1 個單位時間，
商人必須在 (2N?1) 個單位時間穿越出去，
而在經過中間的每個小方格時，都需要繳納一定的費用，
這個商人期望在規定時間內用最少費用穿越出去，
請問至少需要多少費用？
注意：不能對角穿越各個小方格（即，只能向上下左右四個方向移動且不能離開網格），
題目模型
- 子題目：摘花生
- 因為要在（2N-1）個單位時間穿越出去，而從（1，1）走到（n，n）正好需要（2N-1）個單位時間，所以不能走回頭路，
題目代碼
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int n;
int w[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 >> w[i][j];
memset(f, 0x3f, sizeof f); //因為求min，所以初始化為最大，并且需要考慮邊界問題
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= n; j ++ )
{
if(i == 1 && j == 1) f[i][j] = w[i][j]; //(1，1)需在回圈內特判，否則會出錯
else f[i][j] = min(f[i - 1][j], f[i][j - 1]) + w[i][j];
}
cout << f[n][n] << endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/457593.html
標籤：其他
上一篇：Docker快速入門(下)