[UVA][dp] 10337 - Flight Planner
Problem B
Flight Planner
Input: standard input
Output: standard output
Time Limit: 1 second
Memory Limit: 32 MB
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 4001 1 1 11 1 1 11 1 1 11 1 1 11 1 1 11 1 1 11 1 1 11 1 1 11 9 9 11 -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
Frank Hutter
題目描述：
在 x 軸方向是距離，y 軸是高度。
從高度 0 得地方出發，最後落在高度 0 的位置。
可以選擇升或降或不動，要抵抗順逆風的情形，一直往右飛，
其抵抗順逆風的數值取決於不動往右飛的那格。
#include <string.h>
#include <algorithm>
using namespace std;
int main() {
int testcase, X;
int n, i, j;
int g[1005][15];
scanf("%d", &testcase);
while(testcase--) {
scanf("%d", &X);
n = X/100;
for(i = 9; i >= 0; i--)
for(j = 1; j <= n; j++)
scanf("%d", &g[j][i]);
int dp[1005][15];
memset(dp, 63, sizeof(dp));
int oo = dp[0][0];
dp[0][0] = 0;
for(i = 0; i <= n; i++) {
for(j = 0; j < 10; j++) {
if(j+1 < 10)
dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j]+60-g[i+1][j]);
if(j-1 >= 0)
dp[i+1][j-1] = min(dp[i+1][j-1], dp[i][j]+20-g[i+1][j]);
dp[i+1][j] = min(dp[i+1][j], dp[i][j]+30-g[i+1][j]);
}
}
printf("%d\n\n", dp[n][0]);
}
return 0;
}