首页 > ACM题库 > HDU-杭电 > hdu 2217 Visit-动态规划-[解题报告]C++
2014
01-04

hdu 2217 Visit-动态规划-[解题报告]C++

Visit

问题描述 :

Wangye is interested in traveling. One day, he want to make a visit to some
different places in a line. There are N(1 <= N <= 2000) places located at points x1, x2, …, xN (-100,000 ≤ xi ≤ 100,000). Wangye starts at HDU (x = 0), and he travels 1 distance unit in 1 minute . He want to know how many places he could visit at most, if he has T (1 <= T <= 200000 ) minutes.

输入:

The input contains several test cases .Each test case starts with two number N and T which indicate the number of places and the time respectively. Then N lines follows, each line has a number xi indicate the position of i-th place.

输出:

The input contains several test cases .Each test case starts with two number N and T which indicate the number of places and the time respectively. Then N lines follows, each line has a number xi indicate the position of i-th place.

样例输入:

5 16
-3
-7
1
10
8

样例输出:

4
Hint
In the sample, Wangye could visit (-3) first, then goes back to (0), which costs him 6 minutes. Then he visits (1), (8), (10). So he could visit 4 places at most in 16 minutes. :


解题转自:http://www.cnblogs.com/shenyaoxing/archive/2009/10/12/1582023.html


  1. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.

  2. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])