题意：给你一堆二维点，每个点有一些分数。现在要从点（0 , 0 ）出发，只能从标号小的点走到大的点，每个人有一个走的距离的限制，问最后能拿到的最高的分数，当然这个人从（0 , 0）出发还得回到（ 0 , 0 ）。
思路：用dp[i][j]表示在点i分数为j的最短距离，转移方程就是dp[i][j] = min（dp[i][j] , dp[k][j - w[k]] + Map[i][k]） .
CODE:
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define Max 2505
#define FI first
#define SE second
#define ll __int64
#define PI acos（-1.0）
#define inf 0x3fffffff
#define LL（x） （ x 《 1 ）
#define bug puts（"here"）
#define PII pair<int,int>
#define RR（x） （ x 《 1 | 1 ）
#define mp（a,b） make_pair（a,b）
#define mem（a,b） memset（a,b,sizeof（a））
#define REP（i,s,t） for（ int i = （ s ） ; i <= （ t ） ; ++ i ）
using namespace std;
#define N 333
ll x[N] , y[N] , w[N] ;
int n ;
double Map[N][N] ;
double dp[N][11111] ;
double getD（int i , int j） {
return sqrt（1.0 * （x[i] - x[j]） * （x[i] - x[j]） + 1.0 * （y[i] - y[j]） * （y[i] - y[j]）） ;
}
int Asum = 0 ;
int main（） {
int ca = 0 ;
while（cin 》 n , n ） {
Asum = 0 ;
for （int i = 1 ; i <= n ; i ++ ） {
scanf（"%I64d%I64d%I64d",&x[i] ,&y[i],&w[i]） ;
Asum += w[i] ;
}
n ++ ;
x[0] = y[0] = x[n] = y[n] = w[0] = w[n] = 0 ;
for （int i = 0 ; i <= n ; i ++ ） {
for （int j = 0 ; j <= n ; j ++ ） {
Map[i][j] = getD（i , j） ;
}
}
string name ;
int lim ;
printf（"Race %d\n",++ca） ;
while（cin 》 name 》 lim） {
if（name == "#"）break ;
for （int i = 0 ; i <= n ; i ++ ） {
for （int j = 0 ; j <= Asum ; j ++ ）dp[i][j] = inf ;
dp[0][0] = 0 ;
}
for （int i = 1 ; i <= n ; i ++ ） {
for （int j = 0 ; j <= Asum ; j ++ ） {
for （int k = 0 ; k < i ; k ++ ） {
if（w[k] > j）continue ;
dp[i][j] = min（dp[i][j] , dp[k][j - w[k]] + Map[k][i]） ;
}
}
}
int ans = 0 ;
for （int i = 0 ; i <= Asum ; i ++ ） {
if（dp[n][i] <= lim）ans = max（ans , i） ;
}
printf（"%s: %d\n",name.c_str（） ,ans） ;
}
}
return 0 ;
}
/*
5
750 -800 30
1500 0 50
750 750 60
-1250 750 70
-1000 -500 50
Chris 7000
Karl 6500
Tania 5000
# 0
4
500 0 10
0 500 10
-500 0 10
0 -500 10
Hanny 2100
Lizzie 1800
# 0
0
*/ |