# 題目: UVa 10337 - Flight Planner

# 題目說明

你需要為一架飛機規劃最省油的路線 (從起點(0, 0)到終點(0, X))
飛機有3種飛行方式

1. 上升，會耗60的油
2. 平飛，會耗30的油
3. 下降，會耗20的油
   飛行過程中會碰到風阻，負數為逆風，正數為順風

---

INPUT:
輸入一個N，代表有N筆測資
每筆測資第一行輸入一個整數X，代表飛機飛行的距離 (每100為一單位)
接著輸入10 * X個整數，代表每個位置的風阻

---

OUTPUT:
輸出最少的耗油量

# 解題方法

先儲存資料，建立wind風阻的表
將起點dp[0][0]設為0
從起點開始對10 * X表中每一個位置動態規劃

# 參考程式碼

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	// fast io
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int N, X, a;
	vector< vector<int> > wind;
	vector< vector<int> > dp;

	cin >> N;
	while (N--)
	{
		cin >> X, X /= 100;

		// init
		wind.assign(10, vector<int>());
		dp.assign(10, vector<int>(X + 1, 100000));
		dp[0][0] = 0;
		
		// store wind data (up to down)
		for (int i = 9; i >= 0; --i) for (int j = 0; j < X; ++j)
		{
			cin >> a;
			wind[i].emplace_back(a);
		}

		// DP
		for (int j = 1; j <= X; ++j) for (int i = 0; i < 10; ++i)
		{
			int Min = 100000;

			if (i != 0)
			{
				Min = min(Min, dp[i][j - 1] + 30 - wind[i][j - 1]);
				Min = min(Min, dp[i - 1][j - 1] + 60 - wind[i - 1][j - 1]);
			}
			if (i != 9) Min = min(Min, dp[i + 1][j - 1] + 20 - wind[i + 1][j - 1]);

			dp[i][j] = Min;
		}

		cout << dp[0][X] << "\n\n";
	}

	return 0;
}

# 參考資料

https://summon528.github.io/2017/12/13/UVA-10337-Flight-Planner/