题解 P2034 【选择数字】

· · 题解

蒟蒻并没有想到dp做法……于是用最短路做的这道题，跑的dp慢许多。

因为本题需要在每隔最多k个数字就要放弃一个，所以对于每一个数字i，向它后面的i+1~i+k+1连边，之后设一个超级起点s连向1~k，再将n-k+1~n的节点连向一个超级终点t，之后以s为起点跑最短路，所有阶段权值的总和sum减去s到t的距离就是最后的答案。

由于需要连得边数是O(nk)级别的，并且是一个点向一个区间的点连一条边，因此可以用线段树优化建图，讲连的边数变成O(nlogk)，总的时间复杂度是O(nlognlogn)，正好可以卡过1e5的数据

代码：

#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#define mk(x,y) (node){x,y}
using namespace std;

long long sum,ju[400010];
int n,k;
int a[100010],wz[100010];
int nxt[2000010],to[2000010],head[2000100],quan[2000100],gs;
int d[400010],l[400010],r[400010];
vector<int> v;

struct node{int v;long long jv;bool operator <(const node d)const{return jv>d.jv;}};

priority_queue<node> q;

inline void lb(int x,int y,int z){
    nxt[++gs]=head[x];
    head[x]=gs;
    to[gs]=y;
    quan[gs]=z;
}

void build(int x,int li,int ri){
    l[x]=li;r[x]=ri;
    if(li==ri){
        wz[li]=x;
        return;
    }
    int mid=(li+ri)>>1;
    build(x<<1,li,mid);
    build(x<<1|1,mid+1,ri);
    lb(x,x<<1,li==mid?a[li]:0);
    lb(x,x<<1|1,mid+1==ri?a[ri]:0);
}

void query(int x,int li,int ri){
    if(l[x]>ri || r[x]<li)return;
    if(l[x]>=li && r[x]<=ri){v.push_back(x);return;}
    query(x<<1,li,ri);query(x<<1|1,li,ri);
}

void dij(){
    memset(ju,0x3f,sizeof(ju));
    ju[0]=0;
    q.push(mk(0,0));
    while(!q.empty()){
        node dq=q.top();q.pop();
        int x=dq.v;
        if(ju[x]!=dq.jv)continue;
        for(int i=head[x];i;i=nxt[i]){
            if(ju[to[i]]>ju[x]+quan[i]){
                ju[to[i]]=ju[x]+quan[i];
                q.push(mk(to[i],ju[to[i]]));
            }
        }
    }
}

int main(){
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),sum+=a[i];
    build(1,1,n+1);
    for(int i=0;i<=n;i++){
        query(1,i+1,min(i+k+1,n+1));
        for(vector<int>::iterator id=v.begin();id!=v.end();id++){
            lb(wz[i],*id,l[*id]==r[*id]?a[l[*id]]:0);
        }
        v.clear();
    }
    dij();
    printf("%lld",sum-ju[wz[n+1]]);
}