当前位置：首页 > news >正文

【NOIP模拟赛】就反悔贪心

news 来源：原创 2024/5/20 7:33:05

biubiu~~~

这道题，考场上上来就dp然后发现怎么优化也不行.............最后发现是贪心.............

正解：带反悔的贪心，原理是，假设我们现在得到了取i个的最优解那么我们取i+1个的时候要么是新取一个要么把原来取过的点取反（间隙与所选）。我们把所有点从大到小选，这个过程用堆维护，一开始所有的点都是可选的，那么我们取了一个点他前一个后一个都不能再选，那么我们把它们都从堆里取出来，记录答案，同时放进去一个新点，是由这三个点融合的，值为val[i-1]+val[i+1]-val[i]为取反的价值，然后一直取最大取k次就可以了。为什么可以呢：对于一个先取出来的点他左右两点都还没有被取到，因此他如果后来不选了当且仅当同时选其两边的点；这样的话我们满足每次都是在取当前次数下的最大值，这样我们堆里的点的形态大概都是 1 1 1 101 10101 1010101 1 1 1 (1表示没选，0表示选了)。

巨坑：不要错选两边的点，我们只要选了边上的点那么他一定不会被改掉，我们就把他设为inf就当做死人算了，至于为什么会错选呢：我们要选了两边的点，那么我们就会用他的值减去他里面的点的值，然后放进去，我们考虑一下我们就算是选的把点取反那也是选的点数+1的，那我们刚才那个操作是什么鬼？我们要是这么搞就有可能出现以减少所选的点的个数来换取价值的情况。

STL：对于multiset我们删除find到的指针只会删除一个然而我们find到的是我们找到的第一个数。

#pragma G++ optimize("O3")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <set>
#define MAXN 100010
inline void read(long long &sum){
  register char ch=getchar();
  for(sum=0;ch<'0'||ch>'9';ch=getchar());
  for(;ch>='0'&&ch<='9';sum=(sum<<1)+(sum<<3)+ch-'0',ch=getchar());
}
struct Via{
  long long val;
  long long l,r;
  inline friend bool operator < (Via a,Via b){
    return a.val!=b.val?a.val>b.val:a.r<b.r;
  } 
}p[MAXN];
std::set<Via> Set;
long long n,k;
long long ans;
int main(){
  read(n),read(k);
  for(long long i=1,a;i<=n;i++){
    read(a);
    p[i]=(Via){a,i,i};
    Set.insert(p[i]);
  }
  while(k--){
    Via x=*Set.begin();
    Set.erase(Set.find(x));
    long long l=x.l,r=x.r,val=-x.val;
    ans+=x.val;
    if(x.l!=1)
      Set.erase(Set.find(p[x.l-1])),val+=p[x.l-1].val,l=p[x.l-1].l;
    else val-=0x7f7f7f7f;
    if(x.r!=n)
      Set.erase(Set.find(p[x.r+1])),val+=p[x.r+1].val,r=p[x.r+1].r;
    else val-=0x7f7f7f7f;
    x.l=l,x.r=r,x.val=val;
    for(long long i=l;i<=r;i++)p[i]=x;
    Set.insert(x);
  }
  printf("%lld",ans);
}