瞄一眼

显然DP

再瞄一眼

方程就出来了：

设f[ i ][ j ]表示考虑到第 i 颗树，已经种了 j 颗的最大价值.

则 f[ i ][ j ]=max(f[ i-1][ j ]，f[ i-2 ][ j-1]+value[ i ])；

最后看了眼数据..

凉了....

考虑优化

想死也想不出来...........

最后看了题解才懂...

洛沽的（不是我的）

 

---

 

贪心

如果选择一个点种树

那么它两边的点都不能种

当只种 1 颗时

如果选择第 i 个点最优，那就选 i 

种 2 颗时，如果要放弃 i 而选 i 两边的点

那么就一定要两点一起选

因为如果放弃 i 后只选一边的点，那还不如选 i（因为i 的价值肯定大于一边的点，不然前面就不会选 i 了）

而且选了旁边的点更旁边的点就不能选

所以如果放弃 i 就一定要一起选旁边的两点

显然 如果放弃 i 选旁边两点 那么增加的价值为：value[ i-1]+value[ i+1]-value[ i ]

那么我们可以抽象地添加一个点 a ，a=value[ i-1]+value[ i+1]-value[ i ]

如果选了 a 就表示放弃了 i 从而选 i 两边的点

在什么时候添加点 a 呢

显然是在选了点 i 以后..

那么我们就可以贪心了：

选最大的点，更新答案后扔掉，添加 a 到数列里

再选最大的点，一直这样，直到选了 k 个点

（就算选的是抽象出来的点也可以，原因很简单，稍微画个图就懂了）

怎么维护也很简单

开个结构体，用一个堆维护就好了

剩下就是一些细节了，看程序就好了

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;struct node{ long long v,id; bool operator < (const node &b) const{ return v
           
             q;long long n,k,a[500007],l[500007],r[500007],ans;bool pd[500007];int main(){ node p; cin>>n>>k; for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); l[i]=i-1; r[i]=i+1; p.v=a[i]; p.id=i; q.push(p); } int x; while(k--) { while(pd[q.top().id]) q.pop(); p=q.top(); q.pop(); if(p.v<=0) break; //细节，如果出现负数就直接退出，选了反而更小 ans+=p.v; x=p.id; a[x]=a[l[x]]+a[r[x]]-a[x]; pd[l[x]]=pd[r[x]]=1;//细节 l[x]=l[l[x]]; r[x]=r[r[x]];//细节 r[l[x]]=x; l[r[x]]=x;//细节 p.v=a[x]; q.push(p); }//这里有一堆细节 cout<