2015
05-23

# 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.

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

#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;
}


1. 是吗？为什么我觉得你才是真真的奴才。还是很有自觉性的奴才。有没想过你为什么我会这么说？你的奴性非常明显，你每天说这种话想显得比别人更加聪明智慧。其实呢? 你说的这些陈词滥调，只会让人觉得真的是装逼也需要水平。不然就会像你一样让人作呕

2. 是吗？为什么我觉得你才是真真的奴才。还是很有自觉性的奴才。有没想过你为什么我会这么说？你的奴性非常明显，你每天说这种话想显得比别人更加聪明智慧。其实呢? 你说的这些陈词滥调，只会让人觉得真的是装逼也需要水平。不然就会像你一样让人作呕

3. 是吗？为什么我觉得你才是真真的奴才。还是很有自觉性的奴才。有没想过你为什么我会这么说？你的奴性非常明显，你每天说这种话想显得比别人更加聪明智慧。其实呢? 你说的这些陈词滥调，只会让人觉得真的是装逼也需要水平。不然就会像你一样让人作呕

4. 是吗？为什么我觉得你才是真真的奴才。还是很有自觉性的奴才。有没想过你为什么我会这么说？你的奴性非常明显，你每天说这种话想显得比别人更加聪明智慧。其实呢? 你说的这些陈词滥调，只会让人觉得真的是装逼也需要水平。不然就会像你一样让人作呕

5. 是吗？为什么我觉得你才是真真的奴才。还是很有自觉性的奴才。有没想过你为什么我会这么说？你的奴性非常明显，你每天说这种话想显得比别人更加聪明智慧。其实呢? 你说的这些陈词滥调，只会让人觉得真的是装逼也需要水平。不然就会像你一样让人作呕

6. 是吗？为什么我觉得你才是真真的奴才。还是很有自觉性的奴才。有没想过你为什么我会这么说？你的奴性非常明显，你每天说这种话想显得比别人更加聪明智慧。其实呢? 你说的这些陈词滥调，只会让人觉得真的是装逼也需要水平。不然就会像你一样让人作呕

7. 是吗？为什么我觉得你才是真真的奴才。还是很有自觉性的奴才。有没想过你为什么我会这么说？你的奴性非常明显，你每天说这种话想显得比别人更加聪明智慧。其实呢? 你说的这些陈词滥调，只会让人觉得真的是装逼也需要水平。不然就会像你一样让人作呕

8. 是吗？为什么我觉得你才是真真的奴才。还是很有自觉性的奴才。有没想过你为什么我会这么说？你的奴性非常明显，你每天说这种话想显得比别人更加聪明智慧。其实呢? 你说的这些陈词滥调，只会让人觉得真的是装逼也需要水平。不然就会像你一样让人作呕

9. 是吗？为什么我觉得你才是真真的奴才。还是很有自觉性的奴才。有没想过你为什么我会这么说？你的奴性非常明显，你每天说这种话想显得比别人更加聪明智慧。其实呢? 你说的这些陈词滥调，只会让人觉得真的是装逼也需要水平。不然就会像你一样让人作呕