1. 题目

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

题目背景

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

题目描述

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

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

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

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

输入格式

第一行，两个正整数 $N$ 和 $M$。

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

$1$ 表示 yyy，$2$ 表示c01。

输出格式

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

输入输出样例

输入 #1

5 1
1
1
2
2
1

输出 #1

1

说明/提示

难度题，做好心理准备～

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

2. 题解

分析

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

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

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

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

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

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

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

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

代码

#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;
}