3369 膜拜
神牛有很多…当然…每个同学都有自己衷心膜拜的神牛.
某学校有两位神牛，神牛甲和神牛乙。新入学的N位同学们早已耳闻他们的神话。所以，已经衷心地膜拜其中一位了。现在，老师要给他们分机房。但是，要么保证整个机房都是同一位神牛的膜拜者，或者两个神牛的膜拜者人数差不超过M。另外，现在N位同学排成一排，老师只会把连续一段的同学分进一个机房。老师想知道，至少需要多少个机房。输入文件第一行包括N和M。
之后N行，每行一个整数，1表示神牛甲的崇拜者，2表示神牛乙的崇拜者。输出一个整数，表示最小需要机房的数量。
5 1
2 2 1 2 22
对于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#include #include using namespace std;int n,m,a[2501],f[2501];int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) f[i]=2501;//初始化 for(int i=1;i<=n;i++) { int s1=0,s2=0,minn=2501;//s1，当前膜拜1的总人数，s2当前膜拜2的总人数，minn最少可以合并为多少个，即最少房间数 for(int j=i;j;j--) { if(a[j]==1) s1++; else s2++; if(!s1||!s2||abs(s1-s2)<=m) minn=min(minn,f[j-1]+1); } f[i]=minn; } printf("%d",f[n]);}