LG5202 「USACO2019JAN」Redistricting 动态规划+堆/单调队列优化

问题描述

LG5202

题解

\[opt[i]=xx+(cnt[i]-cnt[yy]<=0)\]

发现\(cnt[i]-cnt[yy] <= 0\)只能有两种取值

于是直接堆优化即可

\(\mathrm{Code}\)

#include<bits/stdc++.h>
using namespace std;

template <typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-'){
        fh=-1;ch=getchar();
    }
    else fh=1;
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    x*=fh;
}

const int maxn=300000+7;

int n,k;
int opt[maxn],cnt[maxn];
char s[maxn];

struct node{
    int val,pos;
    bool operator <(node a)const{
        return val==a.val?cnt[pos]>cnt[a.pos]:val>a.val;
    }
};

priority_queue<node>q;

int main(){
    read(n);read(k);cin>>(s+1);
    for(int i=1;i<=n;i++){
        if(s[i]=='H'){
            cnt[i]=cnt[i-1]+1;
        }
        else cnt[i]=cnt[i-1]-1;
    }
    q.push((node){0,0});
    for(int i=1;i<=n;i++){
        while(1){
            int x=q.top().pos;
            if(x>=i-k) break;
            q.pop();
        }
        int xx=q.top().val,yy=q.top().pos;
        opt[i]=xx+(cnt[i]-cnt[yy]<=0);
        q.push((node){opt[i],i});
    }
    printf("%d\n",opt[n]);
    return 0;
}