USACO 2019 JAN Platinum 1 -- Redistricting

发表于 | 更新于 | 分类于 | 评论数：

摘要

Pickupwin 写下了 DP 转移式，略作变形，发现事情十分简单

题面

解

$$
F_i=F_j+Val(j,i)
$$

$$
F_i=F_j+[2(Cnt_i-Cnt_j)\geq i-j]
$$

$$
F_i=F_j+[(2Cnt_i-i)\geq (2Cnt_j-j)]
$$

以 $2Cnt_i-i$ 为下标维护线段树，树内只记录符合要求的 $j$

询问就是两个区间 $max$

由于是取 $max$ 所以要让两两下标不同（不然删除麻烦一点），用 stable_sort 离散化

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <cstdio>
#include <algorithm>

using std::min;
using std::stable_sort;

const int MAXN=300011;
const int INF=1034567890;

char input[MAXN];

int N, K;

int F[MAXN];

int Cnt[MAXN];

int Val[MAXN];

struct Pair{
	int *p, v;
	Pair(){}
	Pair(int *_p, int _v){p=_p;v=_v;}
} P[MAXN];

inline bool operator < (const Pair &A, const Pair &B){
	return A.v<B.v;
}

struct Node{
	int l, r;
	int mn;
} T[MAXN<<2];

void Build(int at, int l, int r){
	T[at].l=l;T[at].r=r;T[at].mn=INF;
	if(l==r)	return;
	int m=(l+r)>>1;
	Build(at<<1, l, m);
	Build((at<<1)|1, m+1, r);
}

void Ins(int at, int p, int v){
	if(T[at].l==T[at].r)	{T[at].mn=v;return;}
	int m=(T[at].l+T[at].r)>>1;
	if(p<=m)	Ins(at<<1, p, v);
	else	Ins((at<<1)|1, p, v);
	T[at].mn=min(T[at<<1].mn, T[(at<<1)|1].mn);
}

int Ask(int at, int l, int r){
	if(T[at].l>=l && T[at].r<=r)	return T[at].mn;
	int m=(T[at].l+T[at].r)>>1;
	int ret=INF;
	if(l<=m)	ret=min(ret, Ask(at<<1, l, r));
	if(r>m)	ret=min(ret, Ask((at<<1)|1, l, r));
	return ret;
}

int main(){
	
	freopen("redistricting.in", "r", stdin);
	freopen("redistricting.out", "w", stdout);
	
	scanf("%d%d", &N, &K);
	scanf("%s", input);
	
	for(int i=1;i<=N;++i)	Cnt[i]=input[i-1]=='G';
	
	for(int i=1;i<=N;++i)	Cnt[i]+=Cnt[i-1];
	
	for(int i=0;i<=N;++i)	Val[i]=(Cnt[i]<<1)-i;
	
	for(int i=0;i<=N;++i)
		P[i]=Pair(&Val[i], Val[i]);
	
	stable_sort(P, P+N+1);
	
	for(int i=0;i<=N;++i)	*P[i].p=i;
	
	Build(1, 0, N);
	
	F[0]=0;
	Ins(1, Val[0], F[0]);
	for(int i=1;i<=N;++i){
		F[i]=min(Ask(1, 0, Val[i])+1, Ask(1, Val[i]+1, N));
		Ins(1, Val[i], F[i]);
		if(i-K>=0)	Ins(1, Val[i-K], INF);
	}
	
	printf("%d\n", F[N]);
	
	return 0;
}