BZOJ4081 : [Wf2014]Skiing

首先将目标点按$y$坐标从小到大排序。

如果加速度为$0$,那么只要贪心走一遍即可。

否则考虑DP,设$f[i][j]$表示从$i$点以速度$j$出发最多能经过多少个点。

注意到将DP值相同的合并可以将$f[i][j]$按$j$划分成$O(n)$段区间,故用区间进行整体转移即可。

在求出DP数组后,再从原点出发,每次贪心选取字典序最小的且能走到最多点数的后继即可。

时间复杂度$O(n^3\log n)$。

#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int N=260,M=N*2;
const double inf=1e20,eps=1e-9;
int _,n,i,j,k,x,y,X,ret,cnt[N],cg;double vy,ma,l,r,vl,vr;
struct P{int x,y,p;}a[N];
struct E{
double l,r;int f;
E(){}
E(double _l,double _r,int _f){l=_l,r=_r,f=_f;}
}f[N][M],g[N*M],h[N*M];
inline bool cmp(const P&a,const P&b){return a.y==b.y?a.p<b.p:a.y<b.y;}
inline bool cmpE(const E&a,const E&b){return a.l<b.l;}
void NO(){
puts("Cannot visit any targets");
exit(0);
}
inline int sgn(double x){
if(x>eps)return 1;
if(x<-eps)return -1;
return 0;
}
inline void cal(int dy,int d,double L,double R){
if(!dy){
if(d){
l=inf,r=-inf;
return;
}
l=L,r=R;
return;
}
double t=dy/vy;
L=max(L,1.0*d/t-ma*t/2);
R=min(R,1.0*d/t+ma*t/2);
if(sgn(L-R)>=0){
l=inf,r=-inf;
return;
}
double A=ma,B=-2.0*ma*t,C=0.5*ma*t*t+L*t-d;
double x=(-B-sqrt(max(B*B-4.0*A*C,0.0)))/(A*2.0);
r=L-ma*x+ma*(t-x);
A=-ma,B=2.0*ma*t,C=-0.5*ma*t*t+R*t-d;
x=(-B+sqrt(max(B*B-4.0*A*C,0.0)))/(A*2.0);
l=R+ma*x-ma*(t-x);
}
inline void merge(){
static int c[N],l[N],r[N];
int i;
for(i=0;i<=n;i++)c[i]=0;
for(i=1;i<=cg;i++)c[n-g[i].f]++;
l[0]=1,r[0]=c[0];
for(i=1;i<=n;i++)l[i]=c[i-1]+1,r[i]=c[i]+=c[i-1];
for(i=1;i<=cg;i++)h[c[n-g[i].f]--]=g[i];
for(i=0;i<=n;i++)if(l[i]<r[i])sort(h+l[i],h+r[i]+1,cmpE);
int m=1;
for(i=2;i<=cg;i++){
if(h[i].f==h[m].f&&sgn(h[m].r-h[i].l)>=0)h[m].r=max(h[m].r,h[i].r);
else h[++m]=h[i];
}
cg=m;
}
inline void go(int x){
int Y,Z=n+1,i,j,k;
for(i=n;i>X;i--)if(a[i].p<Z){
bool flag=0;
for(j=1;j<=cnt[i];j++)if(f[i][j].f==x-1)for(k=1;k<=cg;k++){
cal(a[i].y-a[X].y,a[i].x-a[X].x,g[k].l,g[k].r);
l=max(l,f[i][j].l);
r=min(r,f[i][j].r);
if(sgn(l-r)>=0)continue;
flag=1;
break;
}
if(flag)Y=i,Z=a[i].p;
}
printf("%d",Z);
if(x>1)putchar(' ');
int m=0;
for(j=1;j<=cnt[Y];j++)if(f[Y][j].f==x-1)for(k=1;k<=cg;k++){
cal(a[Y].y-a[X].y,a[Y].x-a[X].x,g[k].l,g[k].r);
l=max(l,f[Y][j].l);
r=min(r,f[Y][j].r);
if(sgn(l-r)>=0)continue;
h[++m]=E(l,r,0);
}
for(i=1;i<=m;i++)g[i]=h[i];
cg=m;
X=Y;
}
int main(){
scanf("%d%lf%lf",&_,&vy,&ma);
while(_--){
scanf("%d%d",&x,&y);
if(y<0)continue;
a[++n].x=x;
a[n].y=y;
}
if(!n)NO();
for(i=1;i<=n;i++)a[i].p=i;
sort(a,a+n+1,cmp);
if(ma<0.5){
for(_=0,i=1;i<=n;i++)if(a[i].x==0){
if(_++)putchar(' ');
printf("%d",a[i].p);
}
if(!_)NO();
return 0;
}
for(i=n;~i;i--){
g[cg=1]=E(-inf,inf,0);
for(j=n;j>i;j--)for(k=1;k<=cnt[j];k++){
cal(a[j].y-a[i].y,a[j].x-a[i].x,f[j][k].l,f[j][k].r);
if(sgn(l-r)>=0)continue;
g[++cg]=E(l,r,f[j][k].f+1);
}
merge();
for(j=1;j<=cg;j++)f[i][j]=h[j];
cnt[i]=cg;
}
for(i=1;i<=cnt[0];i++)if(f[0][i].l<eps&&f[0][i].r>-eps&&f[0][i].f){
ret=f[0][i].f;
break;
}
if(!ret)NO();
g[cg=1]=E(-eps,eps,0);
for(i=ret;i;i--)go(i);
return 0;
}

  

上一篇:php 二位数组按某个键值排序


下一篇:远程连接mysql