首页 > ACM题库 > HDU-杭电 > HDU 4226-Sunday Drive-动态规划-[解题报告]HOJ
2015
05-23

HDU 4226-Sunday Drive-动态规划-[解题报告]HOJ

Sunday Drive

问题描述 :

After wracking your brains at a programing contest on Saturday, you’d like to relax by taking a leisurely Sunday drive. But, gasoline is so expensive nowadays! Maybe, by creatively changing lanes, you can minimize the distance you travel
and save some money!
You will be given a description of several sections of a highway. All sections will have the same number of lanes. Think of your car as a point mass, moving down the center of the lane. Each lane will be 10 feet wide. There are two kinds of highway sections: curved and straight. You can only change lanes on straight sections, and it takes a minimum of 100 feet of the straight section to move over one lane. You can take longer than that, of course, if you choose.
All curve sections will make 90 degree turns. You cannot change lanes on a curve section. In addition, you must be driving along the exact middle of a lane during a turn. So during a turn your position will be 5 feet, or 15 feet, or 25 feet from the edge, etc.
Given a description of a highway, compute the minimum total distance required travel the entire highway, including curves and lane changes. You can start, and end, in any lane you choose. Assume that your car is a point mass in the center of the lane. The highway may cross over/under itself, but the changes in elevation are miniscule, so you shouldn’t worry about their impact on your distance traveled.
In order to be used to cross 2 lanes,

this straight section must be at least 200 feet long.

Simulation?

输入:

There will be several test cases in the input. Each test case will begin with two integers
N M
Where N (1 ≤ N ≤ 1,000) is the number of segments, and M (2 ≤ M ≤ 10) is the number of lanes.
On each of the next N lines will be a description of a segment, consisting of a letter and a number, with a single space between them:
T K
The letter T is one of S, L, or R (always capital). This indicates the type of the section: a straight section (S), a left curve (L) or a right curve (R). If the section is a straight section, then the number K (10 ≤ K ≤ 10,000) is simply its length, in feet. If the section is a right or left curve, then the number K (10 ≤ K ≤ 10,000) is the radius of the inside edge of the highway, again in feet. There will never be consecutive straight sections in the input, but multiple consecutive turns are possible. The input will end with a line with two 0s.

输出:

There will be several test cases in the input. Each test case will begin with two integers
N M
Where N (1 ≤ N ≤ 1,000) is the number of segments, and M (2 ≤ M ≤ 10) is the number of lanes.
On each of the next N lines will be a description of a segment, consisting of a letter and a number, with a single space between them:
T K
The letter T is one of S, L, or R (always capital). This indicates the type of the section: a straight section (S), a left curve (L) or a right curve (R). If the section is a straight section, then the number K (10 ≤ K ≤ 10,000) is simply its length, in feet. If the section is a right or left curve, then the number K (10 ≤ K ≤ 10,000) is the radius of the inside edge of the highway, again in feet. There will never be consecutive straight sections in the input, but multiple consecutive turns are possible. The input will end with a line with two 0s.

样例输入:

3 3
R 100
S 1000
L 100
9 5
S 2500
L 500
S 2000
L 500
S 5000
L 500
S 2000
L 500
S 2500
5 4
L 100
L 100
L 100
L 100
L 100
0 0

样例输出:

1330.07
17173.01
824.67

动态规划题。因为题目有一个地方看错了,赛后才AC。


#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>


using namespace std;


const int maxn = 1111;
const double PI = 3.14159265358979323846;
const double oo = (1 << 30) * 1.0;
char kind[maxn];
double len[maxn];
double dp[maxn][12];
int n, m;


// 计算从第a段的第b条跑道的起点走到第c条跑道的终点所需的最短路程
double calc(int a, int b, int c)
{
    if (kind[a] == 'R' || kind[a] == 'L')
    {
        if (b == c)
        {
            double r;
            if (kind[a] == 'R') // 这里要根据不同的弯道确定半径
                r = (b - 1) * 10.0 + 5 + len[a];
            else r = (m - b) * 10.0 + 5 + len[a];
            return (PI / 2.0 * r);
        }
        else return oo; // 不可达,返回无穷大
    }
    else
    {
        if (len[a] < abs((c - b)) * 100.0) // 最初写的是len[a] < 100.0,就是WA在了这里,题目没看清
            return oo;
        else
            return (sqrt(len[a] * len[a] + (b - c) * 10 * (b - c) * 10));
    }
}


double DP()
{
    for (int i = 0; i <= m; ++i)
        dp[0][i] = 0.0;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            dp[i][j] = oo;
            for (int k = 1; k <= m; ++k)
            {
                dp[i][j] = min(dp[i][j], dp[i-1][k] + calc(i, k, j));
            }
        }
    }
    double ans = oo;
    for (int i = 1; i <= m; ++i)
        ans = min(ans, dp[n][i]);
    return ans;
}


int main()
{
    while (scanf("%d %d", &n, &m))
    {
        if (n == 0 && m == 0)
            break;
        char ch;
        for (int i = 1; i <= n; ++i)
        {
            scanf("\n%c %lf", &kind[i], &len[i]);
        }
        printf("%.2lf\n", DP());
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/ahfywff/article/details/7506187