首页 > ACM题库 > HDU-杭电 > HDU 3562-Interesting Tour[解题报告]HOJ
2014
11-05

HDU 3562-Interesting Tour[解题报告]HOJ

Interesting Tour

问题描述 :

Wuhan University is one of the most beautiful universities in China, and there are many charming scenic spots in the campus. After observing for several years, iSea find an interesting phenomenon of those spots: many old spots were built organically and not according to some architecture plan, but, strangely, their growth exhibits a similar pattern: the cities started from three points of spots, with each pair being connected by a bidirectional street; then, gradually, new points of spots were added. Any new point of spot was connected by two new bidirectional streets to two different previous points of spots which were already directly connected by a street.

A tourist visiting our university would like to do a tour visiting as many points of spots as possible. The tour can start at any point of spot and must end at the same point of spot. The tour may visit each street at most once and each point of spot at most once except the first point of spot.

Searing in the library, iSea have known how the scenic spots grew. Now he want to find the largest number of different points of spots a single tour can visit.

输入:

There are several test cases in the input.

The first line of each case contains three integers N (3 < N <= 1000), indicating the total number of spots.
The next N-3 lines each contain a pair of space-separated integers A, B, indicating that the corresponding point of interest was connected by streets to points A and B. And you can assume both A and B had already connected.

The input terminates by end of file marker.

输出:

There are several test cases in the input.

The first line of each case contains three integers N (3 < N <= 1000), indicating the total number of spots.
The next N-3 lines each contain a pair of space-separated integers A, B, indicating that the corresponding point of interest was connected by streets to points A and B. And you can assume both A and B had already connected.

The input terminates by end of file marker.

样例输入:

4
1 2
5
1 2
1 2

样例输出:

4
4

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int dp[1004][1005] ;
pair < int ,int > p[2000];
int n ;
int main()
{
	while (scanf("%d",&n)!=EOF)
	{
		memset(dp,0,sizeof(dp));
		int ans = 0;
		for (int i = 4 ; i <= n ; i ++)
		{
			scanf("%d%d",&p[i].first,&p[i].second);
		}
		for (int i = n ; i >= 4 ; i --)
		{
			int xx = p[i].first ;
			int yy = p[i].second ;
			ans = max( ans , dp[xx][yy] + dp[xx][i] + dp[yy][i] + 3 );
			dp[xx][yy] = max(dp[xx][yy] , dp[xx][i] + dp[yy][i] + 1 );
			dp[yy][xx] = dp[xx][yy];
		}
		cout << max(ans , dp[1][2]+dp[2][3]+dp[1][3] + 3) << endl;
	}
}

  1. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    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)

  2. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。

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

  4. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮