题解：P5617 [MtOI2019] 不可视境界线

· · 题解

有点板子的题。

题意是有 n 个在坐标轴上的圆，选其中 k 个要求圆面积并最大。

不难发现有状态设计 dp_i 表示选了第 i 个圆，只考虑前 i 个圆，面积并最大是多少。有转移式：dp_i=\max\limits_{j=1}^{i-1}dp_j+\pi r^2-w(j,i) 其中若有面积交则 w(j,i)=2\arccos{\frac{x_i-x_j}{2r}}r^2-(x_i-x_j)\sqrt{r^2-(\frac{x_i-x_j}{2})^2}。

观察一下代价函数，可以写成关于圆心距 d 的函数，观察一下 r=1 时图像

可以发现在正数值域上他是一个凹函数，那么可以写成 f(i)-f(i-1)\geq f(i+1)-f(i)

\iff w(i,j)-w(i+1,j)\geq w(i,j+1)-w(i+1,j+1)

满足四边形不等式，可以套用决策单调性。同时有恰好 k 个的条件可以用wqs二分。复杂度 O(n\log^2n)。

需要注意一下，如果每次现场计算代价，有可能会tle，最好先预处理出圆心距对应的函数值，同时二分的代价是小数。

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;
const double pi=acos(-1);

bool st;
int n,k,r,x[N],L[N],R[N],cnt[N],cntt;
double val[N];
double dp[N],ans;
inline double w(int i,int j) {
    if(i==0) return 0;
    if(x[j]-x[i]>2*r) {return 0;}
    return val[x[j]-x[i]];
}
inline bool check(double mid) {
    deque<int> dq;dq.clear();ans=cntt=0;
    dq.push_back(0);L[0]=1,R[0]=n;dp[0]=cnt[0]=0;
    for(int i=1;i<=n;i++) {
        while(R[dq.front()]<i) dq.pop_front();
        L[dq.front()]=i;
        dp[i]=dp[dq.front()]-w(dq.front(),i)+pi*r*r-mid;
        if(dp[i]-ans>-1e-12) cntt=max(cntt,cnt[dq.front()]+1);
        ans=max(ans,dp[i]);
        cnt[i]=cnt[dq.front()]+1;
        while(!dq.empty()&&dp[dq.back()]-w(dq.back(),L[dq.back()])<dp[i]-w(i,L[dq.back()])) dq.pop_back();
        if(dq.empty()) {dq.push_back(i),L[i]=i,R[i]=n;}
        else if(dp[dq.back()]-w(dq.back(),R[dq.back()])>dp[i]-w(i,R[dq.back()])) {if(R[dq.back()]<n) L[i]=R[dq.back()]+1,R[i]=n,dq.push_back(i);}
        else {
            int ll=L[dq.back()],rr=R[dq.back()],res=rr+1;
            while(ll<=rr) {
                int midd=(ll+rr)>>1;
                if(dp[dq.back()]-w(dq.back(),midd)<dp[i]-w(i,midd)) rr=midd-1,res=midd;
                else if(abs(dp[dq.back()]-w(dq.back(),midd)-(dp[i]-w(i,midd)))<=1e-12&&cnt[dq.back()]<cnt[i]) rr=midd-1,res=midd;
                else ll=midd+1;
            }
            if(res<=n) {
                R[dq.back()]=res-1;
                L[i]=res,R[i]=n;dq.push_back(i);
            }
        }
    }
    return cntt<k;
}
bool ed;

signed main() {
    cerr<<(double)(&st-&ed)/1024/1024<<'\n';
    scanf("%d%d%d",&n,&k,&r);dp[0]=0;
    for(int i=1;i<=n;i++) scanf("%d",&x[i]);
    for(int i=0;i<=2*r;i++) val[i]=2*acos(double(i)/double(2*r))*r*r-i*sqrt(r*r-(double)(i*i)/4);
    double ll=-3e8,rr=3e8,res=ll;
    int num=0;
    while(rr-ll>1e-12&&num<=50) {
        num++;
        double mid=(ll+rr)/2;check(mid);
        if(cntt<k) rr=mid;
        else if(cntt>k) ll=mid,res=mid;
        else {res=mid;break;}
    }
    check(res);
    printf("%0.14lf",ans+res*k);
    return 0;
}