【洛谷 P1484 种树】解题报告

ACM-ICPC

Publish Date: 2018-10-11

题目描述

cyrcyr今天在种树，他在一条直线上挖了n个坑。这n个坑都可以种树，但为了保证每一棵树都有充足的养料，cyrcyr不会在相邻的两个坑中种树。而且由于cyrcyr的树种不够，他至多会种k棵树。假设cyrcyr有某种神能力，能预知自己在某个坑种树的获利会是多少（可能为负），请你帮助他计算出他的最大获利。

输入输出格式

输入格式：

第一行，两个正整数n,k。

第二行，n个正整数，第i个数表示在直线上从左往右数第i个坑种树的获利。

输出格式：

输出1个数，表示cyrcyr种树的最大获利。

输入输出样例

input

6 3
100 1 -1 100 1 -1

output

200

说明

对于20%的数据，n<=20。

对于50%的数据，n<=6000。

对于100%的数据，n<=500000，k<=n/2,在一个地方种树获利的绝对值在1000000以内。

解法：

可以直接DP：

：f[i][j]表示种到第i棵树且种了j棵的最大获利，则f[i][j]=max(f[i-1][j],f[i-2][j-1]+a[i])。
然而这样会T掉，因为最后的数据太大了。

所以就有了贪心的解法：

k=1的时候，显然选最大的(假设为a[i])。
当K=2而的时候，要么选一个与a[i]不相邻的数，要么选a[i-1],a[i+1]。
所以a[i-1],a[i+1]必须同时选或者同时不被选(可以玄学证明一下)。

所以就可以用一个大根堆来维护。

每次取出堆顶，然后ans加上这个值，再把这个数原来的位置上的值变为相邻两个数的和再减去这个位置上的值(表示合并一下这3个数，为了以后要反悔的时候用)。
把取出来的那个数原来的数的相邻两个数标记一下，表示已经不能用了，但是为了防止这两个相邻的数的和会大于原来的数加上除了相邻的数意外任意的数的和。所以就把把它原来的数的相邻的数的和减去原来的数的值如堆(为了可以反悔)。
如此这么操作进行k次，假如堆顶的值小于0，那么就直接退出(加上的话肯定亏了啊)
但是这样有个小(大)问题，怎么样才能快速的求出每个数相邻的数呢？(已经进行了多次)，所以要用一个链表来维护，即分别表示它的左边相邻的数，右边相邻的数。

Talk is cheap,show me your codes:

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

const int maxn=500005;
int n,k,use[maxn];
ll ans,a[maxn];
int l[maxn],r[maxn];

struct Node
{
    ll mark;
    int num;	
};

class Heap
{
    public:
        Node heap[maxn];
        int cnt;
        
        void Set()
        {
            memset(heap,0,sizeof(heap));
            cnt=0;
        }
        
        void Up(int p)
        {
            while(p>1){
                if(heap[p].mark > heap[p/2].mark){
                    swap(heap[p],heap[p/2]);
                    p/=2;
                }
                else break;
            }
        }
        
        void Insert(ll x,int num)
        {
            heap[++cnt].mark=x;
            heap[cnt].num=num;
            Up(cnt);
        }
        
        void Down(int p)
        {
            int s=p<<1;
            while(s<=cnt){
                if(heap[s].mark<heap[s+1].mark && s<cnt) s++;
                if(heap[s].mark > heap[p].mark){
                    swap(heap[s],heap[p]);
                    p=s;s=p<<1;
                }
                else break;
            }
        }
        
        void Remove(int k)
        {
            heap[k].mark=heap[cnt].mark;
            heap[k].num=heap[cnt--].num;
            Up(k);Down(k);
        }
};

Heap d;

/*
inline void Debug()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int x;scanf("%d",&x);
        d.Insert(x,i);		
    }
    for(int i=1;i<=n;i++){
        printf("%d %d\n",d.heap[1].num,d.heap[1].mark);
        d.Remove(1); 
    }
}
*/

inline void Input()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        d.Insert(a[i],i); 
        l[i]=i-1;r[i]=i+1;
    }
}

inline void Work()
{
    r[0]=1;l[n+1]=n;
    for(int i=1;i<=k;i++){//3
        while(use[d.heap[1].num]) d.Remove(1); 
        Node now=d.heap[1];d.Remove(1);
        if(now.mark < 0) break;
        ans+=now.mark;
        int x=now.num;
        a[x]=a[l[x]]+a[r[x]]-a[x];//1.
        now.mark=a[x];
        use[l[x]]=use[r[x]]=1;//2.
        l[x]=l[l[x]];r[l[x]]=x;
        r[x]=r[r[x]];l[r[x]]=x;//4.
        d.Insert(now.mark,now.num);//2. 
    }
    printf("%lld\n",ans);
}

int main()
{
//	Debug();
    Input();
    Work();
    return 0;
}