首页 > 其他 > 详细

luogu P4383 [八省联考2018]林克卡特树lct

时间:2019-06-12 22:05:25      阅读:117      评论:0      收藏:0      [点我收藏+]

传送门

题目操作有点奇怪,不过可以发现这就是把树先变成\(k+1\)个连通块,然后每个连通块选一条路径(本题中一个点也是一条路径),然后依次接起来.所以实际上要求的是选出\(k+1\)条点不相交的路径的最大权值和.可以先考虑暴力,设\(f_{i,j,0/1/2}\)表示第\(i\)个点的子树中,选了\(j\)条路径,点\(i\)当前和\(0/1/2\)个点有连边,转移可以参考代码

然后能发现这个答案随着\(k\)的增长是一个上凸函数,所以可以凸优化dp,即二分选一条路径的代价,然后dp就没有\(j\)的限制,但是要记录选的路径条数,同时选一条路径要减去代价,根据选的路径条数和\(k+1\)的大小关系调整二分边界

//WA代码
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<cmath>
#include<ctime>
#include<queue>
#include<map>
#include<set>
#define LL long long
#define db double

using namespace std;
const int N=2000+10;
const db eps=1e-6;
LL rd()
{
    LL x=0,w=1;char ch=0;
    while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*w;
}
int n;
db aa,bb,a[N],b[N],c[N],f[N],na[N],nb[N];
void cal(db m1,db m2)
{
    for(int i=1;i<=n;++i)
    {
        f[i]=f[i-1],na[i]=na[i-1],nb[i]=nb[i-1];
        if(f[i]<f[i-1]+a[i]-m1) f[i]=f[i-1]+a[i]-m1,na[i]=na[i-1]+1,nb[i]=nb[i-1];
        if(f[i]<f[i-1]+b[i]-m2) f[i]=f[i-1]+b[i]-m2,na[i]=na[i-1],nb[i]=nb[i-1]+1;
        if(f[i]<f[i-1]+c[i]-m1-m2) f[i]=f[i-1]+c[i]-m1-m2,na[i]=na[i-1]+1,nb[i]=nb[i-1]+1;
    }
}

int main()
{
    n=rd(),aa=rd(),bb=rd();
    for(int i=1;i<=n;++i) scanf("%lf",&a[i]);
    for(int i=1;i<=n;++i) scanf("%lf",&b[i]);
    for(int i=1;i<=n;++i) c[i]=1.0-(1.0-a[i])*(1.0-b[i]);
    db l1=0,r1=1,z1,z2;
    while(r1-l1>eps)
    {
        db m1=(l1+r1)/2;
        db l2=0,r2=1;
        while(r2-l2>eps)
        {
            db m2=(l2+r2)/2;
            cal(m1,m2);
            if(nb[n]<=bb) z2=m2,r2=m2-eps;
            else l2=m2+eps;
        }
        cal(m1,z2);
        if(na[n]<=aa) z1=m1,r1=m1-eps; 
        else l1=m1+eps;
    }
    cal(z1,z2);
    printf("%.5lf\n",f[n]+na[n]*z1+nb[n]*z2);
    return 0;
}

luogu P4383 [八省联考2018]林克卡特树lct

原文:https://www.cnblogs.com/smyjr/p/11012838.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!