首页 > ACM题库 > HDU-杭电 > HDU 3516-Tree Construction[解题报告]HOJ
2014
11-05

HDU 3516-Tree Construction[解题报告]HOJ

Tree Construction

问题描述 :

Consider a two-dimensional space with a set of points (xi, yi) that satisfy xi < xj and yi > yj for all i < j. We want to have them all connected by a directed tree whose edges go toward either right (x positive) or upward (y positive). The figure below shows an example tree.

How high is the Building

Write a program that finds a tree connecting all given points with the shortest total length of edges.

输入:

The input begins with a line that contains an integer n (1 <= n <= 1000), the number of points. Then n lines follow. The i-th line contains two integers xi and yi (0 <= xi, yi <= 10000), which give the coordinates of the i-th point.

输出:

The input begins with a line that contains an integer n (1 <= n <= 1000), the number of points. Then n lines follow. The i-th line contains two integers xi and yi (0 <= xi, yi <= 10000), which give the coordinates of the i-th point.

样例输入:

5
1 5
2 4
3 3
4 2
5 1
1
10000 0

样例输出:

12
0

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const int M=1100;

const int INF=1000000000;

int dp[M][M];
int K[M][M];

int x[M];
int y[M];


int get_w(int i,int j,int k)
{
 return x[k+1]-y[j]+y[k]-x[i];
}


int main()
{
 int n;
 while(scanf("%d",&n)==1)
 {
 for(int i=1;i<=n;i++)
 scanf("%d%d",&x[i],&y[i]);
 for(int i=1;i<=n;i++)
 for(int j=i;j<=n;j++)
 dp[i][j]=INF;
 for(int i=1;i<=n;i++)
 dp[i][i]=0;
 memset(K,-1,sizeof(K));
 for(int j=1;j<=n;j++)
 for(int i=j-1;i>=1;i--)
 {

 int low=K[i][j-1];
 int high=K[i+1][j];
 if(low==-1)
 low=i;
 if(high==-1)
 high=j-1;
 for(int k=low;k<=high;k++)
 {
 int w=get_w(i,j,k);
 //cout<<w<<endl;
 if(dp[i][j]>dp[i][k]+dp[k+1][j]+w)
 {
 dp[i][j]=dp[i][k]+dp[k+1][j]+w;
 K[i][j]=k;
 }

 }

 }
 /*for(int i=1;i<=n;i++)
 {
 for(int j=1;j<=n;j++)
 {
 cout<<K[i][j]<<" ";

 }
 cout<<endl;
 }*/
 printf("%d\n",dp[1][n]);
 //cout<<dp[1][n]<<endl;

 }
 return 0;

}

  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。