题意：在一张地图上，有N(N<=1000)个靶子，每个靶子有4个属性，分别是(x,y,t,p)，分别表示这个靶子坐落在点(x,y)（保证所有的靶子不会坐落在同一个点上），它将出现在t时刻，击中它的可能性为p。在0时刻你可以任选一个靶子瞄准，每秒钟你只可以移动一个单位的准星。问在整个游戏过程中，能击中靶子数期望的最大值。
其实，把每个靶子的编号作为点的话，根据时间和距离的关系可以直接形成一个DAG（有向无环图）。然后直接DP就可以了。
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 using namespace std; 5 typedef long long LL; 6 double dp[1010]; 7 struct Node{ 8 int x,y,t; 9 double p; 10 }node[1010]; 11 12 int cmp(Node a,Node b){ 13 return a.t < b.t; 14 } 15 16 bool ok(Node a,Node b){ 17 LL dist = LL(a.x-b.x)*(a.x-b.x)+LL(a.y-b.y)*(a.y-b.y); 18 LL time = LL(a.t-b.t)*LL(a.t-b.t); 19 if(dist <= time) return 1; 20 return 0; 21 } 22 23 int main() 24 { 25 int n; 26 scanf("%d",&n); 27 for(int i = 1;i <= n;i++) 28 scanf("%d%d%d%lf",&node[i].x,&node[i].y,&node[i].t,&node[i].p); 29 sort(node+1,node+n+1,cmp); 30 double ans = 0.0; 31 for(int i = n;i >= 1;i--){ 32 dp[i] = 0; 33 for(int j = i+1;j <= n;j++){ 34 if(ok(node[i],node[j])) dp[i] = max(dp[i],dp[j]); 35 } 36 dp[i] += node[i].p; 37 //printf("dp[%d] = %.6f ",i,dp[i]); 38 ans = dp[i] > ans ? dp[i] : ans; 39 } 40 printf("%.10f ",ans); 41 return 0; 42 }