本文主要是介绍Kattis Redistricting—— 优先队列+dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Description
Input
Output
输出更赛牛较多的或者均势的分区的最小可能数量。
Sample Input
7 2
HGHGGHG
Sample Output
3
题意：
给你一个串，让你把它分成若干个块，每个块的最大长度为k，问你最后H的数量<=G的数量的块最少的可能是多少。
题解：
这道题一看就是dp，由于它的数据是1e5，那么就不太可能是状压和区间了，那么就是普通dp。dp[i]保存的是在第i个点G的数量>=H的数量的划分的最小区间个数。普通dp有一个特点：后面的状态从前面的状态转移过来。那么这道题到第i个点可以由max(0,i-k)到i-1这个区间的值转移过来，那么由哪里转移过来？肯定是最小值了，否则就不会是最优解。但是最小值有可能有多个，举个例子：
9 6
GGGGGGHGH
这种情况，刚开始六个G都是1，后面的第一个H由于能比前面的任何一个大，所以还是1，之后的G，由于前面的H并没有比它多，所以就变成2了，那么到现在为止dp数组是1 1 1 1 1 1 1 2 0，到最后一个数我们改取什么？肯定是HGH最后3个数，这样就可以消掉一个区间，那么我们要取的是前面G-H最大的那个位置。这样的话后面的H-G会最大，那么优先队列就这样排序就好了。
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
char s[N];
int g[N],h[N],dp[N];
struct node
{int val,del,id;bool operator< (const node& a)const{if(val!=a.val)return val>a.val;return del<a.del;}
};
int main()
{int n,k;scanf("%d%d",&n,&k);scanf("%s",s+1);for(int i=1;i<=n;i++)g[i]=g[i-1]+(s[i]=='G'),h[i]=h[i-1]+(s[i]=='H'),dp[i]=1e9;dp[0]=0;priority_queue<node>Q;Q.push({0,0,0});for(int i=1;i<=n;i++){int sta;if(i<k)sta=0;elsesta=i-k;while(Q.top().id<sta)Q.pop();node t;t=Q.top();dp[i]=t.val+(g[i]-g[t.id]>=h[i]-h[t.id]);Q.push({dp[i],g[i]-h[i],i});}printf("%d\n",dp[n]);return 0;
}
这篇关于Kattis Redistricting—— 优先队列+dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
