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

问题描述

题解

\[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;

}

巴特西

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

问题描述

题解

\(\mathrm{Code}\)

最新文章

热门文章