首页 > ACM题库 > HDU-杭电 > HDU 3086-Need for Speed-动态规划-[解题报告]HOJ
2014
03-01

HDU 3086-Need for Speed-动态规划-[解题报告]HOJ

Need for Speed

问题描述 :

Jiaoshou is a fan of “Need for Speed”, a famous game which most people have played. Recently, Jiaoshou had cleared “Need for Speed Undercover”. In this game, Jiaoshou acted as a spy. To prove that he is not a spy, Jiaoshou must do some evil things frequently. So lots of police cars often ran after him. In order to escape from the chase, Jiaoshou need to accelerate his Bugatti Veyron.

To simplify this problem, we just assume that only one police car ran after Jiaoshou. And Bugatti Veyron’s speed is vx. The police car’s speed is vy. v is a function of first degree or a constant, as the form of a*m+b. In this form, m means the minute that the car has run.
Now Jiaoshou is S meters ahead. Jiaoshou like to know if he could escape from the chase. He want you to write a program to solve this problem.

输入:

The input contains several tests. The first line of the input is a single integer T (T<1000) which is the number of test cases. Then T test cases follow.
Each test case contains three lines. The first line contains a single real number S (0<S<=10^6) , as the problem has described. The second line contains two real numbers ax, bx, indicating Bugatti Veyron’s speed is ax*m+bx. The last line also contains two real numbers ay, by, indicating the police car’s speed is ay*m+by. All numbers are range from -1000 to 1000, except S.

输出:

The input contains several tests. The first line of the input is a single integer T (T<1000) which is the number of test cases. Then T test cases follow.
Each test case contains three lines. The first line contains a single real number S (0<S<=10^6) , as the problem has described. The second line contains two real numbers ax, bx, indicating Bugatti Veyron’s speed is ax*m+bx. The last line also contains two real numbers ay, by, indicating the police car’s speed is ay*m+by. All numbers are range from -1000 to 1000, except S.

样例输入:

2
100
0 10
0 20
1000
0 1
0 0

样例输出:

Oh,God!Jiaoshou will be catched after 10.000 minutes.
Good driver,Jiaoshou!

/*
T
dist
ax bx
ay by
追及问题:(ay-ax)/2*m^2 + (by-bx)*m - dist = 0 判断是否有解
*/

#include <iostream>
#include <math.h>
using namespace std;

const double esp = 0.0000000000001;
bool isExistSolution;
double ans1,ans2;

void solve_equation(double a,double b,double c) //ax^2+bx+c=0
{
	if (fabs(a) < esp)
	{
		if (fabs(b) > 0)
		{
			isExistSolution = true;
			ans1 = ans2 = -c / b;		// 分母不能为0!!
		}
		else
			isExistSolution = false;
		return;
	}
	double deltar = b*b - 4.0*a*c;
	if (deltar < 0)
		isExistSolution = false;
	else
	{
		isExistSolution = true;
		deltar = sqrt(deltar)/(2.0*a);
		b = (-b)/(2.0*a);
		ans1 = b + deltar;
		ans2 = b - deltar;
	}
}
int main()
{

#ifndef ONLINE_JUDGE
	freopen("2.txt","r",stdin);
#endif

	int T;
	double dist, ax, bx, ay, by;
	cin >> T;
	while (T--)
	{
		cin >> dist >> ax >> bx >> ay >> by;
		solve_equation(0.5*(ay-ax),by-bx,-dist);
		if (!isExistSolution)
			puts("Good driver,Jiaoshou!");
		else
		{
			if (ans1 > 0)
				printf("Oh,God!Jiaoshou will be catched after %.3lf minutes.\n",ans1);
			else if (ans2 > 0)
				printf("Oh,God!Jiaoshou will be catched after %.3lf minutes.\n",ans2);
			else
				puts("Good driver,Jiaoshou!");
		}
	}
	return 0;
}

参考:http://blog.csdn.net/linraise/article/details/18777521


  1. 样例输出和程序输出不吻合,修改一下样例输出吧。我用的是VC编译器,会提示我的i和j变量重复定义

  2. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish

  3. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测

  4. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)

  5. #!/usr/bin/env python
    def cou(n):
    arr =
    i = 1
    while(i<n):
    arr.append(arr[i-1]+selfcount(i))
    i+=1
    return arr[n-1]

    def selfcount(n):
    count = 0
    while(n):
    if n%10 == 1:
    count += 1
    n /= 10
    return count