HBC24826美丽序列,动态规划,过关题目[USACO 2009 Feb B]Cruel Math Teacher, II题解

挑战自我，勇攀编程高峰！全网最全C++题库，助您成为编程达人。

As if powers of numbers were not cruel enough, Bessie's cruel math teacher has created yet another cruel assignment: Find the 'root' or 'zero' of a polynomial. All of these polynomials have a highest degree D (1

As if powers of numbers were not cruel enough, Bessie's cruel math teacher has created yet another cruel assignment: Find the 'root' or 'zero' of a polynomial. All of these polynomials have a highest degree D (1 <= D <= 11) that is odd and have but a single solution in the range -1,000,000 <= X <= 1,000,000; for that solution, the polynomial's value when evaluated for X is very close or equal to to 0 in computer math. Given a polynomial with real number coefficients (-500 <= coef_i coef i ​ <= 500), find a value of X that is within 0.0005 of the value of X that will yield 0 when the polynomial is evaluated. Multiply that value of X by 1,000 and print it as an (unrounded) integer. By way of example, consider the cubic polynomial problem 1.5*x*x*x - 10 = 0. Astute algebra students will quickly recognize a solution for this as x*x*x = 100/15 = 20/3 = 6.66666. To five decimal places, the exactly solution is 1.88207. For this task, the proper output would be 1882. The polynomial is expressed as the sum from i=0..D of coef_i*x^i (where x^i means x to the i-th power). No answer will require more than six significant digits and each answer will be small enough that it is able to be incremented by 0.0001 in the 'double' precision floating point datatype without losing lots of precision. HINT: Find a strategy to narrow the search space each time you choose a new X value as a guess.

成为编程大师，不再是梦想！全网最全C++题库，助您开启编程新篇章。

标签： HBC24826美丽序列 动态规划 过关题目[USACO 2009 Feb B]Cruel Math Teacher II题解