Bakser's Blog

我是逗比。

bzoj1150 贪心

| Comments

首先最终选取的线段一定是相邻两点间的线段。
很容易想到的贪心思路是每次选取最小的线段然后删除与它有公共端点的线段。
这显然是错误的,样例都过不了。
考虑为什么这样是错的,因为我们发现虽然选取这个最小线段是局部最优的,但它会影响到旁边两个线段的选取,对全局最优造成影响。
那该如何修正?
因为首先如果这条线段比他旁边两条线段中的一条小,那么不会选取到他,所以若产生"后效性",则一定是同时选取它相邻的两条线段在最优方案中。采取“等效替代”的方法,首先正常删掉三条线段,然后添加一条虚拟的线段,长度为被选取线段的左右两条线段长度之和减去被选取线段的长度,这样就相当于添加了一个“决策”,同时选取这条线段也抹去了选取前一条的影响。

bzoj1150
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
#define N 100100
#define mp make_pair
#define INF 0x7f7f7f7f
typedef pair<int,int> pii;
typedef set<pii>::iterator iter;
struct hh
{
    int len,pre,succ;
}a[N];
int n,k,l[N];
long long ans;
set<pii> h;
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",l+i);
        if(i==1)continue;
        a[i].pre=i-1;
        a[i].succ=i+1;
        a[i].len=l[i]-l[i-1];
        h.insert(mp(a[i].len,i));
    }
    a[1].len=INF;
    a[1].succ=2;
    h.insert(mp(INF,1));
    a[n+1].len=INF;
    a[n+1].pre=n;
    h.insert(mp(INF,n+1));
    for(int i=1;i<=k;i++)
    {
        iter it(h.begin());
        ans+=it->first;
        int pos(it->second),pre(a[pos].pre),succ(a[pos].succ);
        a[pos].len=a[pre].len+a[succ].len-a[pos].len;
        a[a[pre].pre].succ=pos;a[pos].pre=a[pre].pre;
        a[a[succ].succ].pre=pos;a[pos].succ=a[succ].succ;
        h.erase(it);
        h.erase(mp(a[pre].len,pre));
        h.erase(mp(a[succ].len,succ));
        h.insert(mp(a[pos].len,pos));
    }
    cout<<ans<<endl;
    return 0;
}

Comments

comments powered by Disqus