OSU
二分$DP$
第一眼
还以为是期望$DP$的原题，白兴奋了。
二分
最大值最小显然二分。
二分速度。（我写的速度平方）
$DP$
在第一遍二分加贪心写挂之后，我开始怀疑它是$DP$可是式子怎么也推不出来，最后把它套二分里发现刚刚好。
$f[i]=max(f[i],f[j]+1)$.
$f[i]$表示选了第$i$个，一共点了$x$个点（得了$x$分）。
二分判断是否可行时，$n$²$DP$就好。
细节
这题有大量细节，因为二分的是$double$的速度，所以无法直接输出答案，可以贪心（乱搞）一下，二分完，枚举点对，看哪个点对之间的速度最接近（小于）二分的结果。这个正确性应该比较显然。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| #include<bits/stdc++.h>
using namespace std;
struct lsqy{
int x,y,t;
}q[10101];
double v[2020][2020];
int f[2010];
int n,k;
bool chk(double x)
{
memset(f,0,sizeof(f));
for(int i=0;i<=n;++i)
for(int j=0;j<i;++j)
if(x-v[i][j]>0.00001)
f[i]=max(f[i],f[j]+1);
for(int i=1;i<=n;++i)
if(f[i]>=k) return 1;
return 0;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i)
{
scanf("%d%d%d",&q[i].t,&q[i].x,&q[i].y);
}
for(int i=0;i<=n;++i)
for(int j=0;j<=i;++j)
v[i][j]=v[j][i]=1.0*((q[i].x-q[j].x)*(q[i].x-q[j].x)+(q[i].y-q[j].y)*(q[i].y-q[j].y))/((q[i].t-q[j].t)*(q[i].t-q[j].t));
double l=0,r=1e9;
while(r-l>0.00001)
{
double mid=(l+r)/2;
if(chk(mid)) r=mid;
else l=mid;
}
int a=1,b,c;
double minn=1e9;
for(int i=0;i<=n;++i)
for(int j=0;j<i;++j)
if(l-v[i][j]>0.0000001)
{
if(minn-(l-v[i][j])>0.000001)
{
minn=l-v[i][j];
b=((q[i].x-q[j].x)*(q[i].x-q[j].x)+(q[i].y-q[j].y)*(q[i].y-q[j].y));
c=abs(q[i].t-q[j].t);
}
}
for(int ls,i=2;i*i<=b;++i)
{
ls=i*i;
if(b%(ls)==0)
{
while(b%ls==0)
{
a*=i;
b/=ls;
}
}
}
int gcc=__gcd(a,c);
printf("%d %d %d",a/gcc,b,c/gcc);
}
|
``
