USACO19JAN Redistricting

题目链接:戳我

一个优先队列优化DP

一定要注意第二关键字的排序啊!!我真的是菜,被坑了好久qwq
设\(f[i]\)表示前i个的最小答案,从前面选择的时候第一关键字是f[j]的大小,第二关键字是要确保[j+1,i]区间产生的贡献尽可能小

#include
#include
#include
#include
#include
#include
#define MAXN 300010
using namespace std;
int n,k;
int f[MAXN],sum[MAXN];
struct Node
{
    int pos,f;
    friend bool operator < (Node x,Node y)
    {
        if(x.f==y.f) return sum[x.pos]>sum[y.pos];
        return x.f>y.f;}
};
priority_queueq;
char s[MAXN];
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("ce.in","r",stdin);
    // freopen("ce.out","w",stdout);
    #endif
    scanf("%d%d",&n,&k);
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='H') sum[i]=sum[i-1]+1;
        else sum[i]=sum[i-1]-1;
    }
    // for(int i=1;i<=n;i++) printf("sum[%d]=%d\n",i,sum[i]);
    q.push((Node){0,0});
    for(int i=1;i<=n;i++)
    {
        while(!q.empty()&&q.top().pos