洛谷P1792——[国家集训队]种树

逃离我推掉我的手 2023-06-05 12:44 106阅读 0赞

传送门：[QAQQAQ][]

题意：$n$个点中选$m$个不相邻的点，使得这些点不相邻（1和n算相邻），求这些点的最大值

思路：这不是神仙题不是神仙题……

刚看到这题觉得不难，好像只要贪心就可以了但贪心不知从何下手——因为取了一个点就会影响其它两个点

所以我们要用“可以反悔”的贪心，即取完一个点以后，我们要加入一个点，让此操作可以反悔——不取这个点，而取它两边的点，即$val\[new\]=val\[l\]+val\[r\]-val\[pos\]$，然后取了当前点把它左右点删去即可（因为再取一次当前点就是取它左右点的情况）（有点像网络流里的残量网络）

这样用一个堆维护，每次取最大值即可

（证明：因为有可以反悔的操作，所以每种情况都可以选到，不会因为取了当前最大值而排除了全局最优解，而每次取的都是合法的切实最大值，所以最终答案一定是最大值）

代码：（推荐比赛的时候先写一个较为稳妥的DP）

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    const int inf=(int)2e8;
    const int N=200005;
    
    int dp[2][2201][1101][2];
    int n,m,a[N],ans=-inf;
    
    void checkmax(int &x,int y)
    {
        if(x<y) x=y;
    }
    
    void subtask1()
    {
        for(int bl=0;bl<=1;bl++)
            for(int i=0;i<=n;i++)
                for(int j=1;j<=m;j++)//之前写成了0 
                    for(int t=0;t<=1;t++) dp[bl][i][j][t]=-inf;
        dp[1][1][1][1]=a[1]; dp[0][1][0][0]=0;
        for(int bl=0;bl<=1;bl++)
        {
            for(int i=2;i<=n;i++)
            {
                for(int j=1;j<=m;j++)
                {
                    if(!(i==n&&bl==1)) dp[bl][i][j][1]=dp[bl][i-1][j-1][0]+a[i];
                    dp[bl][i][j][0]=max(dp[bl][i-1][j][1],dp[bl][i-1][j][0]);//+=!
                    if(j==m)
                    {
                        checkmax(ans,dp[bl][i][j][0]);
                        checkmax(ans,dp[bl][i][j][1]);
                    }
                }
            }
        }
        printf("%d\n",ans);
    }
    
    struct node{
        int l,r,val,id;
        bool operator < (const node &rhs) const{
            return val<rhs.val;
        }
    }t[N];
    
    int vis[N];
    priority_queue<node> q;
    void subtask2()
    {
        int sum=0;
        for(int i=1;i<=n;i++)
        {
            t[i].l=i-1; t[i].r=i+1;
            t[i].val=a[i]; t[i].id=i;
        }
        t[1].l=n; t[n].r=1;
        for(int i=1;i<=n;i++) q.push(t[i]);
        for(int i=1;i<=m;i++)
        {
            while(vis[q.top().id]) q.pop();
            node f=q.top(); q.pop();
            //取出来的node不能直接用，因为它的l,r可能已经改变 
            vis[t[f.id].l]=vis[t[f.id].r]=1;//可以理解成三个点并成了一个点 
            sum+=f.val;
            t[f.id].val=t[t[f.id].l].val+t[t[f.id].r].val-t[f.id].val;
            t[f.id].l=t[t[f.id].l].l;
            t[f.id].r=t[t[f.id].r].r;
            t[t[f.id].r].l=f.id;
            t[t[f.id].l].r=f.id;
            q.push(t[f.id]);
        }
        cout<<sum<<endl;
    }
    
    int main()
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        if(m>n/2)
        {
            puts("Error!");
            return 0;
        }
        if(n<=2100) subtask1();
        else subtask2();
        return 0;
    }

转载于:https://www.cnblogs.com/Forever-666/p/11272887.html

[QAQQAQ]: https://www.luogu.org/problem/P1792
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/9d6bd7f1e3474def996a32f64287c036.png