1. 题目

题目链接：P2418「yyy loves OI IV」 。

题目背景

某校 2015届有两位 OI 神牛，yyy 和 c01。

题目描述

全校除他们以外的 NN 名学生，每人都会膜拜他们中的某一个人。现在老师要给他们分宿舍了。但是，问题来了：

同一间宿舍里的人要么膜拜同一位大牛，要么膜拜 yyy 和 c01 的人数的差的绝对值不超过 MM。否则他们就会打起来。

为了方便，老师让 NN 名学生站成一排，只有连续地站在一起的人才能分进同一个宿舍。

假设每间宿舍能容纳任意多的人，请问最少要安排几个宿舍？

输入格式

第一行，两个正整数 NN 和 MM。

第 2⋯N+12 \cdots N+1 行，每行一个整数 11 或 22，第 ii 行的数字表示从左往右数第 i−1i-1 个人膜拜的大牛。

11 表示 yyy，22 表示c01。

输出格式

一行，一个整数，表示最少要安排几个宿舍。

输入输出样例

输入 #1

1
2
3
4
5
6
5 1
1
1
2
2
1

输出 #1

1
1

说明/提示

难度题，做好心理准备～

测试点编号 N的范围 M的范围
1~3 ≤2,500\leq 2,500 ≤10\leq 10
4~5 ≤500,000\leq 500,000 ≤10\leq 10
6~10 ≤500,000\leq 500,000 ≤2,000\leq 2,000

2. 题解

分析

从第一个同学开始，逐步往最后一个同学扫描；易知除了最后一个宿舍，其余宿舍：

  • 要么全部膜拜同一个大佬
  • 要么二者数量之差的绝对值等于 MM

设 dp[i]dp[i] 表示处理完前 ii 个同学至少需要的宿舍数量，stu[i]stu[i] 表示第 ii 个同学的膜拜的大佬（−1-1 代表 11， 11 代表 22），sum[i]=∑stu[i]sum[i] = \sum stu[i] 表示前 ii 个同学膜拜的大佬的代数数量和（即膜拜两位大佬的数量之差，这便是将 11 和 22 映射为 −1-1 和 11 的原因：方便处理），ump[u]ump[u] 表示对于当前输入，膜拜者二者数量相差绝对值为 uu 时所需的最少宿舍数量（由于 uu 的取值范围较大，故选择 unordered_map 来实现存储记录）。

【注】可以设定 ump[u]ump[u] 的原因在于，最优情况下，所有宿舍出现的情况是一样的，即膜拜数量最多的是同一位大佬（不然由于宿舍数量没有上限，则可以合并相邻膜拜者数量较大的一者不同的宿舍，仍然满足题意条件）。

  • 对于第一种情况：可以通过设定记录上一个不同记录值的位置来实现；即 dp[i]≤dp[last]+1dp[i] \leq dp[last] + 1，其中 lastlast 为与同学 ii 膜拜的大佬相对的上一个同学的位置。即处理到当前同学，最多比上一个信仰不同的同学的宿舍数量多 11（因为此时两者之间的同学膜拜的都是同一个大佬）。

  • 对于第二种情况：dp[i]≤ump[abs(sum[i])−M]+1dp[i] \leq ump[abs(sum[i]) - M] + 1，即至少小于等于比现在少 MM 个数量差的情况下所需最少宿舍数量 +1+1 。

因此，对于 u≤0u \leq 0 而言，ump[u]=0ump[u] = 0。因为 abs(sum[i])−M≤0abs(sum[i]) - M \leq 0 说明此时膜拜二者的数量差还没有超过 MM ，因此此时最多需要 11 个宿舍，即 ump[abs(sum[i])−M]=0ump[abs(sum[i]) - M] = 0。

综合二者，则可以列出状态转移方程：dp[i]=min(dp[last]+1,ump[abs(sum[i])−M]+1)dp[i] = min(dp[last]+1, ump[abs(sum[i]) - M] + 1)。最终结果即为 dp[n]dp[n] 。

代码

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
95
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6 + 5;

int stu[MAXN], sum[MAXN], dp[MAXN];

//终极快读
char buf[1<<22],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<22,stdin),p1==p2)?EOF:*p1++)

//快读
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
	{
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
	{
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

void input(int n) {
    for(int i = 1; i <= n; ++i) {
        int a = read();
        stu[i] = 2*a - 3;
    }
} 

int myabs(int x) {
    return x < 0 ? -x : x;
}

void init(int n) {
    for(int i = 1; i <= n; ++i) {
        sum[i] = sum[i-1] + stu[i];
    }
}

unordered_map <int,int> ump;
void update(int u, int x) {
    if(u > 0) {
        if(ump.count(u) == 0) {
            ump[u] = x;
        } else {
            ump[u] = min(ump[u], x);
        }
    }
}

int query(int u) {
    if(ump.count(u) == 0) {
        if(u <= 0) {
            return 0; 
        } else {
            return MAXN;
        }
    }
    return ump[u]; 
}

int answer(int n, int m) {
    int last1 = 0, last2 = 0;
    for(int i = 1; i <= n; ++i) {
        if(stu[i] == 1) {
            dp[i] = dp[last2] + 1;
            last1 = i;
        } else {    
            dp[i] = dp[last1] + 1;
            last2 = i;
        }
        dp[i] = min(dp[i], query(myabs(sum[i])-m)+1);
        update(myabs(sum[i]), dp[i]);
    }
    return dp[n];
}

int main() 
{
    int n, m;
    scanf("%d%d", &n, &m);
    input(n);
    init(n);
    printf("%d\n", answer(n,m));
    return 0;
}