1. 题目
题目链接:P2418「yyy loves OI IV」 。
题目背景
某校 2015届有两位 OI 神牛,yyy 和 c01。
题目描述
全校除他们以外的 N 名学生,每人都会膜拜他们中的某一个人。现在老师要给他们分宿舍了。但是,问题来了:
同一间宿舍里的人要么膜拜同一位大牛,要么膜拜 yyy 和 c01 的人数的差的绝对值不超过 M。否则他们就会打起来。
为了方便,老师让 N 名学生站成一排,只有连续地站在一起的人才能分进同一个宿舍。
假设每间宿舍能容纳任意多的人,请问最少要安排几个宿舍?
输入格式
第一行,两个正整数 N 和 M。
第 2⋯N+1 行,每行一个整数 1 或 2,第 i 行的数字表示从左往右数第 i−1 个人膜拜的大牛。
1 表示 yyy,2 表示c01。
输出格式
一行,一个整数,表示最少要安排几个宿舍。
输入输出样例
输入 #1
输出 #1
说明/提示
难度题,做好心理准备~
测试点编号 |
N的范围 |
M的范围 |
1~3 |
≤2,500 |
≤10 |
4~5 |
≤500,000 |
≤10 |
6~10 |
≤500,000 |
≤2,000 |
2. 题解
分析
从第一个同学开始,逐步往最后一个同学扫描;易知除了最后一个宿舍,其余宿舍:
- 要么全部膜拜同一个大佬
- 要么二者数量之差的绝对值等于 M
设 dp[i] 表示处理完前 i 个同学至少需要的宿舍数量,stu[i] 表示第 i 个同学的膜拜的大佬(−1 代表 1, 1 代表 2),sum[i]=∑stu[i] 表示前 i 个同学膜拜的大佬的代数数量和(即膜拜两位大佬的数量之差,这便是将 1 和 2 映射为 −1 和 1 的原因:方便处理),ump[u] 表示对于当前输入,膜拜者二者数量相差绝对值为 u 时所需的最少宿舍数量(由于 u 的取值范围较大,故选择 unordered_map
来实现存储记录)。
【注】可以设定 ump[u] 的原因在于,最优情况下,所有宿舍出现的情况是一样的,即膜拜数量最多的是同一位大佬(不然由于宿舍数量没有上限,则可以合并相邻膜拜者数量较大的一者不同的宿舍,仍然满足题意条件)。
-
对于第一种情况:可以通过设定记录上一个不同记录值的位置来实现;即 dp[i]≤dp[last]+1,其中 last 为与同学 i 膜拜的大佬相对的上一个同学的位置。即处理到当前同学,最多比上一个信仰不同的同学的宿舍数量多 1(因为此时两者之间的同学膜拜的都是同一个大佬)。
-
对于第二种情况:dp[i]≤ump[abs(sum[i])−M]+1,即至少小于等于比现在少 M 个数量差的情况下所需最少宿舍数量 +1 。
因此,对于 u≤0 而言,ump[u]=0。因为 abs(sum[i])−M≤0 说明此时膜拜二者的数量差还没有超过 M ,因此此时最多需要 1 个宿舍,即 ump[abs(sum[i])−M]=0。
综合二者,则可以列出状态转移方程:dp[i]=min(dp[last]+1,ump[abs(sum[i])−M]+1)。最终结果即为 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; }
|