P1564 膜拜【洛谷算法习题】-开发者社区

P1564 膜拜

网页链接

P1564 膜拜

题目描述

神牛有很多…当然…每个同学都有自己衷心膜拜的神牛。

某学校有两位神牛，神牛甲和神牛乙。新入学的n nn位同学们早已耳闻他们的神话。

所以，已经衷心地膜拜其中一位了。现在，老师要给他们分机房。但是，要么保证整个机房都是同一位神牛的膜拜者，或者两个神牛的膜拜者人数差不超过m mm。另外，现在n nn位同学排成一排，老师只会把连续一段的同学分进一个机房。老师想知道，至少需要多少个机房。

输入格式

输入文件第一行包含两个整数n nn和m mm。

第2 22到第( n + 1 ) (n + 1)(n+1)行，每行一个非1 11即2 22的整数，第( i + 1 ) (i + 1)(i+1)行的整数表示第i ii个同学崇拜的对象，1 11表示甲，2 22表示乙。

输出格式

输出一个整数，表示最小需要机房的数量。

输入输出样例 #1

输入 #1

5 1 2 2 1 2 2

输出 #1

说明/提示

数据规模与约定

对于30 % 30\%30%的数据，保证1 ≤ n ≤ 50 1 \le n \le 501≤n≤50，0 ≤ m ≤ 50 0 \le m \le 500≤m≤50。
对于100 % 100\%100%的数据，保证1 ≤ n ≤ 2500 1 \le n \le 25001≤n≤2500，0 ≤ m ≤ 2500 0 \le m \le 25000≤m≤2500。

解题思路

本题是线性 DP + 前缀和的最少划分问题。将同学序列划分为若干连续段，每段要么信仰相同，要么两种信仰人数差不超过m mm，求最少段数。采用动态规划，以d p [ i ] dp[i]dp[i]表示前i ii人所需的最少机房数，通过枚举上一个分割点并利用前缀和快速判断区间合法性，实现O ( n 2 ) O(n^2)O(n2)的转移。

1. 问题等价转化

划分条件：对于一个区间[ l , r ] [l, r][l,r]，设信仰甲（1）的人数为c n t 1 cnt_1cnt1，信仰乙（2）的人数为c n t 2 cnt_2cnt2。该区间能成为一个机房的充要条件是：
- 全部信仰相同：c n t 1 = 0 cnt_1 = 0cnt1=0或c n t 2 = 0 cnt_2 = 0cnt2=0；
- 或人数差不超过m mm：∣ c n t 1 − c n t 2 ∣ ≤ m |cnt_1 - cnt_2| \le m∣cnt1−cnt2∣≤m。
目标：将整个序列划分为若干满足条件的连续区间，求最少的区间数量。
状态定义：令d p [ i ] dp[i]dp[i]表示前i ii个同学所需的最少机房数。初始d p [ 0 ] = 0 dp[0] = 0dp[0]=0，d p [ 1 ] = 1 dp[1] = 1dp[1]=1（单个同学必然自成一个机房）。
转移方程：对于i ii从1 11到n nn，枚举上一个分割点j jj（0 ≤ j < i 0 \le j < i0≤j<i），若区间( j + 1 , i ] (j+1, i](j+1,i]合法，则：
d p [ i ] = min ⁡ ( d p [ i ] , d p [ j ] + 1 ) dp[i] = \min(dp[i], dp[j] + 1)dp[i]=min(dp[i],dp[j]+1)
最终答案为d p [ n ] dp[n]dp[n]。

2. 算法实现：前缀和优化判断

前缀和预处理：
- sum[1][i]：前i ii人中信仰1 11的人数。
- sum[2][i]：前i ii人中信仰2 22的人数。
  则区间[ j + 1 , i ] [j+1, i][j+1,i]的信仰人数差为：
  d i f f = ( s u m [ 2 ] [ i ] − s u m [ 2 ] [ j ] ) − ( s u m [ 1 ] [ i ] − s u m [ 1 ] [ j ] ) diff = (sum[2][i] - sum[2][j]) - (sum[1][i] - sum[1][j])diff=(sum[2][i]−sum[2][j])−(sum[1][i]−sum[1][j])
  判断条件：abs(diff) <= m或sum[2][i] - sum[2][j] == 0或sum[1][i] - sum[1][j] == 0。
DP 过程：
- 初始化dp数组为无穷大，d p [ 0 ] = 0 dp[0] = 0dp[0]=0。
- 外层循环i = 1 ∼ n i = 1 \sim ni=1∼n，内层循环j = i − 1 ∼ 0 j = i-1 \sim 0j=i−1∼0。
- 若区间合法，则d p [ i ] = min ⁡ ( d p [ i ] , d p [ j ] + 1 ) dp[i] = \min(dp[i], dp[j] + 1)dp[i]=min(dp[i],dp[j]+1)。
- 由于n ≤ 2500 n \le 2500n≤2500，O ( n 2 ) O(n^2)O(n2)的复杂度完全可行。

3. 复杂度分析

时间复杂度：O ( n 2 ) O(n^2)O(n2)，最坏约6.25 × 10 6 6.25 \times 10^66.25×106次操作，在n ≤ 2500 n \le 2500n≤2500时非常快。
空间复杂度：O ( n ) O(n)O(n)，存储前缀和与 DP 数组。

总结

通过 DP 求解最少划分段数，用前缀和O ( 1 ) O(1)O(1)判断任意区间是否满足机房分配条件。遍历所有可能的分割点取最小值，实现简单直观，完美适配数据范围。

代码简要说明

输入与初始化：读入n , m n, mn,m，将d p dpdp数组初始化为极大值，d p [ 0 ] = 0 , d p [ 1 ] = 1 dp[0]=0, dp[1]=1dp[0]=0,dp[1]=1。读入每个同学的信仰，同时更新两种信仰的前缀和数组sum[1]和sum[2]。
DP 转移：
- 对于每个i ii，倒序枚举j jj从i − 1 i-1i−1到0 00。
- 计算区间两种信仰的人数差diff。
- 若abs(diff) <= m或区间内只有单一信仰，则用d p [ j ] + 1 dp[j] + 1dp[j]+1更新d p [ i ] dp[i]dp[i]。
输出：输出d p [ n ] dp[n]dp[n]。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;constll MAXN=2510;ll n,m;ll sum[3][MAXN];ll dp[MAXN];ll a[MAXN];intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n>>m;for(ll i=0;i<=n+5;i++)dp[i]=INF;dp[0]=0;dp[1]=1;for(ll i=1;i<=n;i++){cin>>a[i];sum[a[i]][i]=sum[a[i]][i-1]+1;sum[(!(a[i]-1))+1][i]=sum[(!(a[i]-1))+1][i-1];}for(ll i=1;i<=n;i++){for(ll j=i-1;j>=0;j--){ll diff=(sum[2][i]-sum[1][i])-(sum[2][j]-sum[1][j]);if(abs(diff)<=m||(sum[2][i]-sum[2][j]==0)||(sum[1][i]-sum[1][j]==0)){dp[i]=min(dp[i],dp[j]+1);}}}cout<<dp[n]<<endl;return0;}