首页 > ACM题库 > HDU-杭电 > HDU 3825-Splendid Moment Collector[解题报告]HOJ
2015
04-13

HDU 3825-Splendid Moment Collector[解题报告]HOJ

Splendid Moment Collector

问题描述 :

Being a traveler is always an exciting and memorable experience, especially for iSea. He is a crazy Splendid Moment Collector, not only he likes the wonderful scenery very much, what’s more, he wants himself go through the moment at the very time!
Saving the Princess

Our beautiful country has N scenic spots, which can be treated as some single points with a coordinate (Xi, Yi), and as a clever prophet, iSea knows the splendid moment of each spots Ti, and he must arrive this spot exactly at Ti time if he want to collect this spot’s splendid moment.
iSea has a speed of V, while travelling between spots, obviously he will choose the shortest path: the straight line. In the beginning, he can choose any spot to start his journey, but in the end, he must return the spot he chooses at first.
Perfectionist pushes himself to gather everything all the time, so does iSea. However, life can’t stand by you the whole days. So iSea wonders the maximum number of splendid moments he can collect, and in all of these journeys have the maximum number, he expects to choose the one has the shortest distance.

输入:

The first line contains a single integer T, indicating the number of test cases.
Each test case begins with two integers N, V. Their meanings are the same as the description.
Then N lines follow, each line contains three integers Xi, Yi, Ti, their meanings are also mentioned in the description.

Technical Specification

1. 1 <= T <= 50
2. 1 <= N <= 100
3. 1 <= V <= 1000
4. 1 <= Ti <= 100000
5. 1 <= Xi, Yi <= 10000

输出:

The first line contains a single integer T, indicating the number of test cases.
Each test case begins with two integers N, V. Their meanings are the same as the description.
Then N lines follow, each line contains three integers Xi, Yi, Ti, their meanings are also mentioned in the description.

Technical Specification

1. 1 <= T <= 50
2. 1 <= N <= 100
3. 1 <= V <= 1000
4. 1 <= Ti <= 100000
5. 1 <= Xi, Yi <= 10000

样例输入:

3
2 2
1 1 1
1 3 2
3 2
1 1 1
2 2 2
1 3 2
3 2
1 1 1
2 2 2
1 3 3

样例输出:

Case 1: 2 4.000
Case 2: 2 2.828
Case 3: 3 4.828

#include<stdio.h>
#include<math.h>
#include<string>
#include<algorithm>

using namespace std;

struct node
{
 double x , y; int time;
} a[1000];

int n , v;
int f[1000] ; double d[1000] , dis[200][200];

int cmp(node p , node q)
{
 if (p.time < q.time) return 1;
 return 0;
}

double dist(int p , int q)
{
 return sqrt( (a[p].x - a[q].x) * (a[p].x - a[q].x) + (a[p].y - a[q].y) * (a[p].y - a[q].y));
}

void pre_deal()
{
 int i , j;
 for (i=1;i<=n;i++)
 for (j=i+1;j<=n;j++)
 dis[i][j] = dist(i , j);
}
void deal()
{
 int i , j , k , ans1; double ans2 , t;
 pre_deal();
 ans1 = 0;
 for(i=1;i<=n;i++)
 {
 memset(f , 0 , sizeof(f));
 f[i] = 1; d[i] = 0;
 for (j=i+1;j<=n;j++) d[j]=1e10;
 for (j=i+1;j<=n;j++)
 if (dis[i][j]/v-1e-8 <= a[j].time - a[i].time)
 {
 if (f[j] < f[i] + 1 || f[j] == f[i] + 1 && d[j] > d[i] + dis[i][j])
 {
 f[j] = f[i] + 1;
 d[j] = d[i] + dis[i][j];
 }
 for (k=j+1;k<=n;k++)
 if (f[k] < f[j] + 1 || f[k] == f[j] + 1 && d[k] > d[j] + dis[j][k])
 if (dis[j][k] / v - 1e-8 <= a[k].time - a[j].time)
 {
 f[k] = f[j] + 1;
 d[k] = d[j] + dis[j][k];
 }
 }
 for (j=i;j<=n;j++)
 {
 t = dis[i][j];
 if (f[j] > ans1 || f[j] == ans1 && d[j] + t < ans2)
 {
 ans1 = f[j]; ans2 = d[j] + t;
 }
 }
 }
 printf("%d %.3lf\n", ans1 , ans2);
}
void init()
{
 int i;
 scanf("%d%d", &n , &v);
 for(i=1;i<=n;i++)
 {
 scanf("%lf%lf%d",&a[i].x,&a[i].y, &a[i].time);
 }
 sort(a+1 , a+n+1 ,cmp);
}

int main()
{
 
 int tot;
 scanf("%d", &tot);
 for (int i=1;i<=tot;i++)
 {
 printf("Case %d: " , i); 
 init();
 deal();
 }
 

}