洛谷 P1484/P1792/P3620 种树/数据备份 题解【堆】【贪心】

点击量：252

    这个题妥妥的三倍经验啊……只贴一个题面好了。

目录

题目描述

A城市有一个巨大的圆形广场，为了绿化环境和净化空气，市政府决定沿圆形广场外圈种一圈树。

 

园林部门得到指令后，初步规划出\(n\)个种树的位置，顺时针编号\(1\)到\(n\)。并且每个位置都有一个美观度\(A_i\)，如果在这里种树就可以得到这\(A_i\)的美观度。但由于A城市土壤肥力欠佳，两棵树决不能种在相邻的位置（\(i\)号位置和\(i+1\)号位置叫相邻位置。值得注意的是\(1\)号和\(n\)号也算相邻位置！）。

 

最终市政府给园林部门提供了\(m\)棵树苗并要求全部种上，请你帮忙设计种树方案使得美观度总和最大。如果无法将\(m\)棵树苗全部种上，给出无解信息。

 

输入输出格式

输入格式：

输入的第一行包含两个正整数\(n,m\)。第二行\(n\)个整数\(A_i\)。

 

输出格式：

输出一个整数，表示最佳植树方案可以得到的美观度。如果无解输出“Error!”，不包含引号。

 

输入输出样例

输入样例#1：

7 3
1 2 3 4 5 6 7

输出样例#1：

15

输入样例#2：

7 4
1 2 3 4 5 6 7

输出样例#2：

Error!

说明

对于全部数据:\(m\le n\)；

\(-1000\le A_i\le 1000\)

N的大小对于不同数据有所不同：

数据编号	N的大小	数据编号	N的大小
1	30	11	200
2	35	12	2007
3	40	13	2008
4	45	14	2009
5	50	15	2010
6	55	16	2011
7	60	17	2012
8	65	18	199999
9	200	19	199999
10	200	20	200000

题解：

    这其实是一道堆优化的题，需要先推一个贪心结论，剩下的难点就是代码实现。应该这些不能取相邻元素的题，都可以用这种方法做了吧。

    一开始可能会想，我把所有树排序，每次选最大的，如果左右有被选过的就不选，但是这样就不能保证合法且最优了。比如说这样的数据：

4 2
4 5 4 0

    如果上来就选择5，那么两个4就不能选了，所以不能直接从大的选。但是我们可以证明，如果最大的不选，那么这棵树两边的树都得选。否则只选一个，并没有选中间的这个对答案的贡献大，而且选择中间这个对选择其他的树的影响更小。如下图：

    而如果同时选上两边的，虽然会对外侧有影响，但是产生的贡献会比单个5多，因此可以考虑备选。但是这样就有选择了，貌似转化为了一个DP问题。不过实际上，选择了两个4，就多选了1个，这三个位置可以转化为：选1个的贡献是5，选2个的贡献是8。而本身选了5，两个4就不能选，那么我们就可以在选择了5之后把4,5,4合并起来，作为一个新的节点，贡献为3，原本的5可以直接计入答案，进行下一个子问题。

    这样就变成了贪心问题，每次选择序列中贡献最大的节点，合并它及左右的两个为一个节点。维护序列用链表就可以了，维护贡献最大的点可以用堆。不过被合并的点要从堆中删除，这里数据范围都不大，用懒惰删除就可以了。

    种树这个题是环形，在输入完毕后把链表首尾相连就可以了。而另外两个题需要注意左右边界问题。

Code of 种树：

#include<cstdio>
#include<cstring>
struct node
{
    node *pre,*nxt;
    long long key;
    bool del;
    node(long long key)
    {
        this->key=key;
        del=0;
        pre=NULL;
        nxt=NULL;
    }
    node()
    {
        del=0;
        pre=NULL;
        nxt=NULL;
    }
}*head,*heap[200100];
int l=0;
void push(node *x)//指针好像放不进stl的优先队列
{
    heap[++l]=x;
    int i=l;
    node *tmp;
    while(i>1&&heap[i]->key>heap[i>>1]->key)
    {
        tmp=heap[i];
        heap[i]=heap[i>>1];
        heap[i>>1]=tmp;
        i>>=1;
    }
    return;
}
void pop()
{
    heap[1]=heap[l--];
    int i=1;
    node *tmp;
    while((i<<1)<=l&&(heap[i]->key<heap[i<<1]->key||heap[i]->key<heap[i<<1|1]->key))
        if((i<<1)==l||heap[i<<1]->key>heap[i<<1|1]->key)
        {
            tmp=heap[i];
            heap[i]=heap[i<<1];
            heap[i<<1]=tmp;
            i<<=1;
        }
        else
        {
            tmp=heap[i];
            heap[i]=heap[i<<1|1];
            heap[i<<1|1]=tmp;
            i=i<<1|1;
        }
    return;
}
node *Insert(node *p,long long x)//在链表的p后面插入x元素
{
    node *tmp=new node(x);
    tmp->pre=p;
    tmp->nxt=p->nxt;
    p->nxt->pre=tmp;
    p->nxt=tmp;
    return tmp;
}
void Delete(node *p)
{
    p->del=1;
    p->pre->nxt=p->nxt;
    p->nxt->pre=p->pre;
}
int a[201000];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    if(2*m>n)
    {
        puts("Error!");
        return 0;
    }
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    head=new node();
    node *tail1=new node(a[1]),*p;
    push(tail1);
    tail1->nxt=new node();
    tail1->pre=head;
    head->nxt=tail1;
    for(int i=2;i<=n;++i)//一开始把链表中的所有元素放进去
    {
        p=Insert(tail1,a[i]);
        tail1=p;
        push(p);
    }
    head=head->nxt;
    tail1->nxt=head;
    head->pre=tail1;
    long long ans=0;
    for(int i=1;i<=m;++i)
    {
        p=heap[1];
        while(p->del)
        {
            pop();
            p=heap[1];
        }
        pop();
        ans+=p->key;
        p->key=p->pre->key+p->nxt->key-p->key;//更新价值并把两边的元素删掉
        Delete(p->pre);
        Delete(p->nxt);
        push(p);
    }
    printf("%lld\n",ans);
    return 0;
}