题目描述 Description

神牛有很多…当然…每个同学都有自己衷心膜拜的神牛.
某学校有两位神牛,神牛甲和神牛乙。新入学的N位同学们早已耳闻他们的神话。所以,已经衷心地膜拜其中一位了。
现在,老师要给他们分机房。
但是,要么保证整个机房都是同一位神牛的膜拜者,或者两个神牛的膜拜者人数差不超过M。
另外,现在N位同学排成一排,老师只会把连续一段的同学分进一个机房。老师想知道,至少需要多少个机房。

 
输入描述 Input Description

输入文件第一行包括N和M。
之后N行,每行一个整数,1表示神牛甲的崇拜者,2表示神牛乙的崇拜者。

 
输出描述 Output Description

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

 
样例输入 Sample Input

5 1 

2  


2

样例输出 Sample Output

2

 
数据范围及提示 Data Size & Hint

对于30%的数据,有1≤N,M≤50;
对于100%的数据,有1≤N,M≤2500

本题可以转化为:将一段区间上的所有的点合并,求最少可以合并为多少的区间。

假设区间f[1,4]有4个点:

1、若最后2个能合并,即合并f[3,4],那么合并后的区间数a=f[1,2]+1,最后2个点合并为1个区间,就是那个1;f[1,2]暂且不管。

2、若最后3个能合并,即合并f[2,4],那么合并后的区间数b=f[1,1]+1,最后3个点合并为1个区间,就是那个1;f[1,1]暂且不管。

3、若最后4个能合并,即合并f[1,4],那么合并后的区间数c=f[1,0]+1,很明显,c=1.

请看加红色的部分,发现什么了吗?他们都是从1开始的,这在后面会用到

那么我为什么要倒着看区间能否合并呢?

因为动态规划递推到f[1,4]时,已经计算完了f[1,3],f[1,3]的值是有3个点时最优的,计算f[1,3]之前就计算完了f[1,2],f[1,2]的值是有2个点是最优的,以此类推。

倘若正着判断,我算区间f[1,4],首先看前2个能否合并,即f[1,4]=f[1,2]+f[3,4],前2个若能合并f[1,2]=1,但f[3,4]并不知道。

由此看出倒着推的好处是:另一个区间是从1开始的,而且这个区间在这之前已经确定了最优值,可以实现O(1)复杂度确定上面a、b、c的值(就是直接用)。而正着推得话,可以看到,前面f[3,4]是区间中的一段,不能直接利用,而且f[3,4]的最优解是什么,我们并不知道。

所以动态转移方程:

设当前要排队的区间为f[1,n],那么f[1,n]=min(f[1,m]+1),1<m<=n

初始化条件:答案数组ans[]除0外,都置为极大值,所以不能用memset(ans,127,sizeof(ans))。为什么呢?因为在循环计算f[1,k]时,是通过f[1,k-1]得到前几个的最优值。f[1,1]就可以通过f[0]递推得到,继而推出后面所有的。

那就有人有疑问了:我memset(ans,127,sizeof(ans))之后,另置f[1,1]=1,从第2个开始往后推,不就行了吗?答案是完全可以,个人习惯所致

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,a[],f[];
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
for(int i=;i<=n;i++) f[i]=;//初始化
for(int i=;i<=n;i++)
{
int s1=,s2=,minn=;//s1,当前膜拜1的总人数,s2当前膜拜2的总人数,minn最少可以合并为多少个,即最少房间数
for(int j=i;j;j--)
{
if(a[j]==) s1++;
else s2++;
if(!s1||!s2||abs(s1-s2)<=m)
minn=min(minn,f[j-]+);
}
f[i]=minn;
}
printf("%d",f[n]);
}
04-21 00:51