「ICPC World Finals 2019」美丽的桥梁

可以得到一个Naive的暴力方法来判断在((L,R))上修桥是否合法:

显然的性质: 如果有相交，则一定存在一个关键点相交

设得到的圆半径为(r=frac{x_R-x_L}{2})，圆心为((x,y)=(frac{x_L+x_R}{2},h-r))

枚举每个(iin [L,R])判断是否点(x_i,y_i)是否相交，如果相交，只需要满足

(y_i>y)，且其与圆心距离(>r)

[ ]

考虑优化判断，将生成的拱形分为左右两部分，分别考虑即可

推论: 对于每个(L)，其左半边不相交的半径为描述为一个范围([0,A_L])

同理的，对于每个(R)也是如此，能求得一个范围([0,B_R])

考虑对于每个(L)，枚举每个(i>L) 来求出(A_L)

设半径为(r)，列出圆心与点(x_i,y_i)距离的表达式，必须满足距离(leq r)，就能得到一个二次方程

二次方程的解集为(x_1,x_2)，但是实际上([0,x_1])这一段不满足(y_i>y)，因此也是合法的

即将每次求得的([0,x_2])区间取交集即可

复杂度为(O(n^2))

同理求得每个(B_R)

考虑朴素的dp，令(dp_i)表示解决了([1,i])前缀的最小代价

枚举(j)，(O(1))判断((i,j))是否合法，然后进行转移

tips: 题目的代价计算方法可能没讲清楚。。。

复杂度为(O(n^2))

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
typedef double db;
typedef long long ll;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,const T &b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,const T &b){ ((a<b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) if(IO=='-') f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=1e4+10;
const db eps=1e-9;
const ll INF=4e18;

int n,h,a,b;
int X[N],Y[N];
db L[N],R[N];
db Sqr(db x){ return x*x; }
ll dp[N];

int main(){
	n=rd(),h=rd(),a=rd(),b=rd();
	rep(i,1,n) X[i]=rd(),Y[i]=rd();
	rep(i,1,n) {
		L[i]=min((db)(X[n]-X[i])/2,(db)(h-Y[i]));
		rep(j,i+1,n) {
			if(X[j]-X[i]>L[i]+eps) break;
			db a=1,b=2*(X[i]-X[j]+Y[j]-h),c=Sqr(X[i]-X[j])+Sqr(Y[j]-h);
			db d=sqrt(b*b-4*a*c);
			db r=(-b+d)/(2*a);
			cmin(L[i],r);
		}
		L[i]*=2;
	}
	rep(i,1,n) {
		R[i]=min((db)(X[i]-X[1])/2,(db)(h-Y[i]));
		drep(j,i-1,1) {
			if(X[i]-X[j]>R[i]+eps) break;
			db a=1,b=2*(X[j]-X[i]+Y[j]-h),c=Sqr(X[j]-X[i])+Sqr(Y[j]-h);
			db d=sqrt(b*b-4*a*c);
			db r=(-b+d)/(2*a);
			cmin(R[i],r);
		}
		R[i]*=2;
	}
	dp[1]=1ll*a*(h-Y[1]);
	rep(i,2,n) {
		dp[i]=INF;
		drep(j,i-1,1) {
			if(X[i]-X[j]>R[i]+eps) break;
			if(X[i]-X[j]>L[j]+eps) continue;
			cmin(dp[i],dp[j]+1ll*a*(h-Y[i])+1ll*(X[i]-X[j])*(X[i]-X[j])*b);
		}
	}
	if(dp[n]<INF) printf("%lld
",dp[n]);
	else puts("impossible");
}