首页 > ACM题库 > HDU-杭电 > HDU 4765-Tsp-动态规划-[解题报告]HOJ
2015
09-17

HDU 4765-Tsp-动态规划-[解题报告]HOJ

Tsp

问题描述 :

MGG is a poor truckman. One day he is asked to deliver packages for customers. There are n customers, where each customer specifies a location to pick up his/her package, and a location to deliver the package. Customers are labeled from 1 to n. For customer i, we denote the pickup location as i+, and the delivery location as i-. To deliver package for customer i, Mo must visit i+ before visiting i-.

However, the truck Mo drives has only a rear door, so the truck works as a stack: the last picked up package must be delivered first. If there are two packages i and j in the truck, and i is picked up before j, then i cannot be delivered unless j is delivered.

Mo knows all the coordinates of pickup and delivery locations. However, due to the censorship of the Great Fire Wall, Mo cannot visit any location more than once. What’s worse, there are additional restrictions:

– Mo can’t go to location j+ from i+ if j > i;
– Mo can’t go to location j- from i- if j < i;
– If Mo has visited location i-, location j+ will be removed from the world and cannot be visited any more if j < i.

Now Mo can choose any location to start. He wants to choose a shortest path to deliver packages for all the n customers. Please find the shortest path for him.

输入:

There are multiple test cases.
For each test case, the first line is an integer n, 0 < n <= 100.
Then n lines follow. There are 4 integers in each line. The integers in the i-th line indicate the x and y coordinates of i+, and the x and y coordinates of i-, respectively.

The distance between two locations is the Euclidean distance between them.

Input is terminated by end-of-file.

输出:

There are multiple test cases.
For each test case, the first line is an integer n, 0 < n <= 100.
Then n lines follow. There are 4 integers in each line. The integers in the i-th line indicate the x and y coordinates of i+, and the x and y coordinates of i-, respectively.

The distance between two locations is the Euclidean distance between them.

Input is terminated by end-of-file.

样例输入:

3
1 3 5 2
2 4 2 3
6 0 2 2
5
5 0 6 0
2 0 5 0
7 0 1 0
6 0 9 0
4 0 6 0

样例输出:

1+ 1- 3+ 2+ 2- 3-
2+ 1+ 1- 2- 3+ 3- 5+ 4+ 4- 5-

题目大意:在100个点中的图中,要求现在选择一条路径遍历所有点,而且,加了很多限制条件。

分析:在比赛的时候以为是图论,然后看了一下,比赛的时候以为这么多条件,才100个点,那么我们就爆搜一下吧,赛后一看别人的tle代码,都是爆搜,幸亏比赛的时候被其他题目卡着没时间写这道题目,额

解法:赛后看了清华的代码,终于给我找到一份比较简洁的代码,发现做法是区间dp。

分析一下题目中的条件,可以得出几点结论

(1)放置点的顺序是递减的。

(2)一个区间一定可以分成多个区间的最优解的组合

用dp[a][b][c] 表示从c+开始操作完从a到b的区间所需要的最小值。

如果这个时候c == b 那么我们根据前面的推论,所以说一定这个区间是由c开始 由c结束,所以就从dp[a][b-1][x]递推过来,这个时候枚举一下起点。

如果c != b ,那么这个时候,因为起点在这个区间的中间,所以说由两个子区间组成,dp[a][c][c] 和dp[c+1][b][x],这个时候x枚举一下起点就可以了。

总共是o(n^3)的复杂度 ,同时记录一下前面转移来的前驱 就可以输出解了。

参考:http://blog.csdn.net/qq564690377/article/details/12177529