题目链接：点击打开链接
给定n个气球
下面n行 x y t val 表示气球出现的坐标(x,y) 出现的时刻t，气球的价值val
枪每秒移动1个单位的距离
问：
射击的最大价值，开始时枪瞄准的位置任意。
思路：
dp一下。。
#include #include #include #include #include #include #include #include using namespace std; #define ll long long #define N 2005 ll n; struct node{ ll x,y,t; double val; }a[N]; bool cmp(node aa, node bb){ return aa.t >n){ for(i = 1; i <= n; i++) cin>>a[i].x>>a[i].y>>a[i].t>>a[i].val; sort(a + 1, a + 1 + n, cmp); for(i = 1; i <= n; i++) { for(j = i+1; j <= n; j++) dis[i][j] = dis[j][i] = dist(a[i],a[j]); } for(i = 1; i <= n; i++) { dp[i] = a[i].val; for(j = 1; j < i; j++) { if(dis[i][j] > ((a[i].t-a[j].t)*(a[i].t-a[j].t))) continue; dp[i] = max(dp[i], dp[j]+a[i].val); } } double ans = 0; for(i = 1; i <= n; i++) ans = max(ans, dp[i]); printf("%.10lf\n",ans); } return 0; }