P1564 膜拜网页链接P1564 膜拜题目描述神牛有很多…当然…每个同学都有自己衷心膜拜的神牛。某学校有两位神牛神牛甲和神牛乙。新入学的n nn位同学们早已耳闻他们的神话。所以已经衷心地膜拜其中一位了。现在老师要给他们分机房。但是要么保证整个机房都是同一位神牛的膜拜者或者两个神牛的膜拜者人数差不超过m mm。另外现在n nn位同学排成一排老师只会把连续一段的同学分进一个机房。老师想知道至少需要多少个机房。输入格式输入文件第一行包含两个整数n nn和m mm。第2 22到第( n 1 ) (n 1)(n1)行每行一个非1 11即2 22的整数第( i 1 ) (i 1)(i1)行的整数表示第i ii个同学崇拜的对象1 11表示甲2 22表示乙。输出格式输出一个整数表示最小需要机房的数量。输入输出样例 #1输入 #15 1 2 2 1 2 2输出 #12说明/提示数据规模与约定对于30 % 30\%30%的数据保证1 ≤ n ≤ 50 1 \le n \le 501≤n≤500 ≤ m ≤ 50 0 \le m \le 500≤m≤50。对于100 % 100\%100%的数据保证1 ≤ n ≤ 2500 1 \le n \le 25001≤n≤25000 ≤ 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 0cnt10或c n t 2 0 cnt_2 0cnt20或人数差不超过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]0d p [ 1 ] 1 dp[1] 1dp[1]1单个同学必然自成一个机房。转移方程对于i ii从1 11到n nn枚举上一个分割点j jj0 ≤ j i 0 \le j i0≤ji若区间( j 1 , i ] (j1, i](j1,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 ] [j1, i][j1,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 ni1∼n内层循环j i − 1 ∼ 0 j i-1 \sim 0ji−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≤2500O ( 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]。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;constll MAXN2510;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);cinnm;for(ll i0;in5;i)dp[i]INF;dp[0]0;dp[1]1;for(ll i1;in;i){cina[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 i1;in;i){for(ll ji-1;j0;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);}}}coutdp[n]endl;return0;}
)
