Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1278
Calculating the minimal cost for a flight involves calculating an optimal flight-altitude depending on wind-strengths changing with different altitudes. It’s not enough just to ask for the route with optimal wind-strength, because due to the mass of a plane you need a certain amount of fuel to rise. Moreover due to safety regulations it’s forbidden to fly above a certain altitude and you can’t fly under zero-level. In order to simplify the problem for now, we assume that for each 100 miles of flight you have only three possiblities: to climb one mile, to hold your altitude or to sink one mile. Climb flight requires 60 units of fuel, holding your altitude requires 30 units and sinking requires 20 units. In the case of headwind you need more fuel while you can save fuel flying with tailwind. Windstrength w will satisfy the condition −10 ≤ w ≤ 10, where negative windstrength is meant to be headwind and positive windstrength is tailwind. For one unit of tailwind you can save one unit of fuel each 100 miles; each unit of headwind will cost an extra unit of fuel. For example to climb under conditions of windstrength w = −5, you need 65 units of fuel for this 100 miles. Given the windstrengths on different altitudes for a way from here to X, calculate the minimal amount of fuel you need to fly to X. Input The first line of the input file contains the number N of test cases in the file. The first line of each test case contains a single integer X, the distance to fly, with 1 ≤ X ≤ 100000 miles and X is a multiple of 100. Notice that it’s not allowed to fly higher than 9 miles over zero and that you have to decide whether to climb, hold your altitude or to sink only for every 100 miles. For every mile of allowed altitude (starting at altitude 9 down to altitude 0) there follow X 100 windstrengths, starting with the windstrength at your current position up to the windstrength at position X − 100 in steps of 100 miles. Test cases are separated by one or more blank lines. Output For each test case output the minimal amount of fuel used flying from your current position (at altitude 0) to X (also at altitude 0), followed by a blank line
. Sample Input 2 400 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 9 9 1 1 -9 -9 1 1000 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 7 7 7 7 7 7 7 7 7 7 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5 -7 -3 -7 -7 -7 -7 -7 -7 -7 -7 -9 -9 -9 -9 -9 -9 -9 -9 -9 -9
Sample Output 120 354
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t,dist,v;
cin >> t;
while(t--){
cin >> dist;
dist/=100;
deque < vector<int>> wind;
for(int i=0;i < 10;i++){
vector<int> row;
for(int j=0;j < dist;j++){
cin >> v;
row.push_back(v);
}
wind.push_front(row);
}
vector<int> dp(10,1e7);
dp[0] = 0;
for(int i=0;i < dist;i++){
vector<int> dpNext(10,0);
for(int j=0;j < 10;j++){
int fromBelow = j==0 ? 1e7 : (dp[j-1] + 60 - wind[j-1][i]);
int fromAbove = j==9 ? 1e7 : (dp[j+1] + 20 - wind[j+1][i]);
int stay = dp[j] + 30 - wind[j][i];
dpNext[j] = min(stay, min(fromBelow, fromAbove));
}
dp = dpNext;
}
printf("%d\n\n",dp[0]);
}
}Input
400
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 9 9 1
1 -9 -9 1
1000
9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9
7 7 7 7 7 7 7 7 7 7
-5 -5 -5 -5 -5 -5 -5 -5 -5 -5
-7 -3 -7 -7 -7 -7 -7 -7 -7 -7
-9 -9 -9 -9 -9 -9 -9 -9 -9 -9
Output
354
Demonstration
UVA Online Judge solution - 10337 - Flight Planner - UVA Online Judge solution in C,C++,java