有关于分治时处理多个最值

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

cinccout @ 2023-11-14 15:33:58

蒟蒻理解，多个最值时所求下标的 dp_i-xi 和所求 dp_k-xk 应该是一样的吧，所以直接带入 k 求值即可，那为什么 link 的提交是错的，而 link 的提交是对的啊awa

前者的实现：

int main()
{
    int k,aa,bb,cc;cin>>n>>k;k++;
    memset(head,-1,sizeof(head));
    for(int i=1;i<n;i++)
    {
        scanf("%d%d%d",&aa,&bb,&cc);
        add(aa,bb,cc);add(bb,aa,cc);
    }
    long long L=-1e13,R=1e13;
    long long pos=0,fans=0;
    while(L<=R)
    {
        long long mid=(L+R)>>1;dfs(1,0,mid);
        dpv ans=max(dp[1][0],max(dp[1][1],dp[1][2]));
        //cout<<mid<<"is"<<ans.val<<" "<<ans.x<<endl;
        if(ans.x>k) L=mid+1;
        else//k增加，最小值位置变小 
        {
            R=mid-1;pos=mid;
            fans=ans.val+k*mid;
        }
    }
    cout<<fans;
    return 0;
}

后者的实现：

//...
//前面的部分相同
int main()
{
    int k,aa,bb,cc;cin>>n>>k;k++;
    memset(head,-1,sizeof(head));
    for(int i=1;i<n;i++)
    {
        scanf("%d%d%d",&aa,&bb,&cc);
        add(aa,bb,cc);add(bb,aa,cc);
    }
    long long L=-1e13,R=1e13;
    long long pos=0,fans=0;
    while(L<=R)
    {
        long long mid=(L+R)>>1;dfs(1,0,mid);
        dpv ans=max(dp[1][0],max(dp[1][1],dp[1][2]));
        //cout<<mid<<"is"<<ans.val<<" "<<ans.x<<endl;
        if(ans.x>k) L=mid+1;//k增加，最小值位置变小 
        else
        {
            R=mid-1;pos=mid;
            fans=ans.val+ans.x*mid;
        }
    }
    cout<<fans;
    return 0;
}

萌新刚学 wqs 二分，求大佬解答！

by Rosaya @ 2023-11-14 15:52:50

能不能发一下 dpv 类型中 max 是怎么取的？

by Rosaya @ 2023-11-14 16:00:59

您可以先看一下前面帖子里的回复。

by cinccout @ 2023-11-14 16:13:25

@Rosaya 唔完整代码

#include<bits/stdc++.h>
using namespace std;
const long long inf=2e18+23542;
int head[300005],cnt,n;
struct qxx{int to,next,len;}a[600005];
void add(int aa,int bb,int cc)
{
    a[++cnt].to=bb;a[cnt].len=cc;
    a[cnt].next=head[aa];head[aa]=cnt;
}
struct dpv
{
    long long val;int x;
    friend bool operator <(dpv x,dpv y)
    {return x.val==y.val?x.x<y.x:x.val<y.val;}
    friend dpv operator +(dpv x,dpv y)
    {return (dpv){x.val+y.val,x.x+y.x};}
}dp[300005][3];
void dfs(int u,int fa,long long val)
{
    dp[u][1]=(dpv){-inf,0};
    dp[u][0]=(dpv){0,0};dp[u][2]={-val,1};
    for(int i=head[u];i!=-1;i=a[i].next)
    {
        int v=a[i].to;
        if(v==fa) continue;
        dfs(v,u,val);dpv tmp[3],tp;
        tp=max(max(dp[v][0],dp[v][1]),dp[v][2]);
        for(int j=0;j<3;j++) tmp[j]=dp[u][j]+tp;
        for(int j=0;j<2;j++) for(int k=0;k<2;k++)
        {
            int num=(j!=0)+(k!=0);
            tmp[j+1]=max(tmp[j+1],dp[u][j]+dp[v][k]+
            (dpv){a[i].len-1ll*(1-num)*val,1-num});
        }
        for(int j=0;j<3;j++)
        dp[u][j]=tmp[j];
    }
}
int main()
{
    int k,aa,bb,cc;cin>>n>>k;k++;
    memset(head,-1,sizeof(head));
    for(int i=1;i<n;i++)
    {
        scanf("%d%d%d",&aa,&bb,&cc);
        add(aa,bb,cc);add(bb,aa,cc);
    }
    long long L=-1e13,R=1e13;
    long long pos=0,fans=0;
    while(L<=R)
    {
        long long mid=(L+R)>>1;dfs(1,0,mid);
        dpv ans=max(dp[1][0],max(dp[1][1],dp[1][2]));
        //cout<<mid<<"is"<<ans.val<<" "<<ans.x<<endl;
        if(ans.x>k) L=mid+1;
        else//k增加，最小值位置变小 
        {
            R=mid-1;pos=mid;
            fans=ans.val+k*mid;
        }
    }
    cout<<fans;
    return 0;
}

另外前面哪个帖子提到这个了啊qwq

by Rosaya @ 2023-11-14 16:21:16

@cinccout 就是您这个 max 实际上是在值相同的时候选择了那个选的东西大的，导致实际上能切到的点被认为没切到。

改成

friend bool operator <(dpv x,dpv y)
    {return x.val==y.val?x.x>y.x:x.val<y.val;}

就过了。

by Rosaya @ 2023-11-14 16:22:26

https://www.luogu.com.cn/discuss/570796

https://www.luogu.com.cn/discuss/113936

这两个帖子都有吧。

by cinccout @ 2023-11-14 16:48:55

@Rosaya 哦哦明白了谢谢！刚才没找到同类型帖子对不起！