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

hdu 2373 Forest-动态规划-[解题报告]C++

Forest

问题描述 :

Bruce Force is standing in the forest. He wonders what is the tree trunk the farthest away which is not blocked from his view by other tree trunks.

Bruce has made a map of the trees in the forest. The map shows his current position as the origin of a cartesian coordinate system. Tree i is shown on the map as a circle with the center (xi, yi) and radius ri. You may assume that a tree trunk is visible if and only if there exists a line segment on the map from the origin (0,0) to a point on the border of the circle representing the tree trunk, where the line segment does not intersect or touch another circle.

输入:

The input contains several test cases. The first line of each test case contains one number n (1 ≤ n ≤ 1000), where n specifies how many trees are on the map. The following n lines contain 3 integers xi, yi, ri each, (-10000 ≤ xi, yi ≤ 10000 , 1 ≤ ri ≤ 1000 ) where (xi, yi) is the center of the circle representing tree trunk i, and ri is the radius of the circle. You may assume that no two circles in the input intersect, i.e., for any two circles, the distance between their centers is more than the sum of their radii. Moreover, you may assume that no circle contains the origin.

The last test case is followed by a line containing one zero.

输出:

The input contains several test cases. The first line of each test case contains one number n (1 ≤ n ≤ 1000), where n specifies how many trees are on the map. The following n lines contain 3 integers xi, yi, ri each, (-10000 ≤ xi, yi ≤ 10000 , 1 ≤ ri ≤ 1000 ) where (xi, yi) is the center of the circle representing tree trunk i, and ri is the radius of the circle. You may assume that no two circles in the input intersect, i.e., for any two circles, the distance between their centers is more than the sum of their radii. Moreover, you may assume that no circle contains the origin.

The last test case is followed by a line containing one zero.

样例输入:

3
10 10 11
1 1 1
-20 -10 20
5
1 2 2
-2 1 1
2 -1 1
-1 -2 2
10000 -10000 1000
0

样例输出:

3.142
1.236

Hint
In the second test case, the first four trees block the view of all trees farther away than these four trees.

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<queue>
#include<algorithm>

using namespace std;

#define INF 0x3ffffff
#define MAXN 1010

struct node
{
	int to;
	int dis;
	int next;
}edge[MAXN*MAXN];

int head[MAXN],en;
bool in[MAXN];
int s[MAXN];
int n,m,dis[MAXN];
int dp[MAXN];

void add(int u,int v,int w)
{
    edge[en].to=v;
    edge[en].dis=w;
    edge[en].next=head[u];
    head[u]=en++;

    edge[en].to=u;
    edge[en].dis=w;
    edge[en].next=head[v];
    head[v]=en++;
}

void spfa(int s)
{
	queue<int> q;
	for(int i=1;i<=n;i++)
	{
		dis[i]=INF;
		in[i]=false;
	}
	dis[s]=0;
	in[s]=true;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		in[u]=false;
		q.pop();
		for(int i=head[u];i!=-1;i=edge[i].next)
		{
			int v=edge[i].to;
			if(dis[u]+edge[i].dis<dis[v])
			{
				dis[v]=dis[u]+edge[i].dis;
				if(!in[v])
				{
					q.push(v);
					in[v]=true;
				}
			}
		}
	}
}


int dag_dp(int u)
{
    if(dp[u]!=-1) return dp[u];
    int tmp=0;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(dis[v]<dis[u]) tmp+=dag_dp(edge[i].to);
    }
    return dp[u]=tmp;
}
int main()
{
    while(~scanf("%d",&n)&&n)
    {
        scanf("%d",&m);
        memset(head,-1,sizeof(head));en=0;
        int u,v,w;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
        }
        spfa(2);
        memset(dp,-1,sizeof(dp));
        dp[2]=1;
        dag_dp(1);
        printf("%d\n",dp[1]);
    }
    return 0;
}

解题转自:http://blog.csdn.net/lenleaves/article/details/9026783


  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  2. for(int i=1; i<=m; i++){
    for(int j=1; j<=n; j++){
    dp = dp [j-1] + 1;
    if(s1.charAt(i-1) == s3.charAt(i+j-1))
    dp = dp[i-1] + 1;
    if(s2.charAt(j-1) == s3.charAt(i+j-1))
    dp = Math.max(dp [j - 1] + 1, dp );
    }
    }
    这里的代码似乎有点问题? dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false

  3. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。