乱写...想出这么一个神奇做法：

假设k无限大，那么这是一个很简单的dp题

在这个dp中我们是可以得到这个最优的树坑的情况的

那么答案只可能出现在这些树坑中（？

因此如果树坑的数量 < k，那么我们只需选取前k个获利最大的树坑求和即为答案了。

但是只得30pts，有可能是码力不足，也有可能是思路错了。求证明QwQ

# include <stdio.h>
# include <iostream>
# include <bits/stdc++.h>

using namespace std;

int v[300005];
int dp[300005][2];

bool cmp(int x,int y)
{
  return v[x] > v[y];
}

int main (void)
{
  int n,k;
  scanf ("%d %d",&n,&k);

  for (int i=1;i<=n;i++)
  {
    scanf ("%d",&v[i]);
  }

  dp[1][0] = 0;
  dp[1][1] = v[1];

  for (int i=2;i<=n;i++)//dp过程
  {
    dp[i][0] = max(dp[i-1][1],dp[i-1][0]);
    dp[i][1] = v[i] + dp[i-1][0];
  }

  int ans_p[300005];
  int len=0;
  
  //求树根位置
  for (int i=n;i>=1;)
  {
    if (dp[i][1] > dp[i][0])
    {
      ans_p[len++] = i;
      i -= 2;
    }
    else
    {
      i--;
    }
  }
  //统计答案
  if (len > k)
  {
    sort(ans_p,ans_p+len,cmp);
    int ans=0;
    for (int i=0;i<k;i++)
    {
      ans += v[ans_p[i]];
    }
    printf ("\n%d",ans);
  }
  else
  {
    printf ("%d",max(dp[n][0],dp[n][1]));
  }

  return 0;
}