P2418「yyy loves OI IV」
P2418「yyy loves OI IV」
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说明/提示
难度题，做好心理准备～
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]的原因在于，最优情况下，所有宿舍出现的情况是一样的，即膜拜数量最多的是同一位大佬（不然由于宿舍数量没有上限，则可以合并相邻膜拜者数量较大的一者不同的宿舍，仍然满足题意条件）。
- 对于第一种情况：可以通过设定记录上一个不同记录值的位置来实现；即 \leq dp[last] + 1，其中 last 为与同学 i 膜拜的大佬相对的上一个同学的位置。即处理到当前同学，最多比上一个信仰不同的同学的宿舍数量多1（因为此时两者之间的同学膜拜的都是同一个大佬）。
- 对于第二种情况： \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;
}