Description
神牛有很多…当然…每个同学都有自己衷心膜拜的神牛.
某学校有两位神牛,神牛甲和神牛乙。新入学的N 位同学们早已耳闻他们的神话。
所以,已经衷心地膜拜其中一位了。现在,老师要给他们分机房。但是,要么保证整个机房都是同一位神牛的膜拜者,或者两个神牛的膜拜者人数差不超过M。另外,现在N位同学排成一排,老师只会把连续一段的同学分进一个机房。老师想知道,至少需要多少个机房。
Input
输入文件第一行包括 N 和 M。
之后 N 行,每行一个整数,1 表示神牛甲的崇拜者,2 表示神牛乙的崇拜者。
Output
输出一个整数,表示最小需要机房的数量。
Range
对于30%的数据,有1 ≤ N ,M≤ 50;
对于100%的数据,有1 ≤ N,M ≤ 2500。
Solution
把问题转化一下,将2改成-1,就变成了要分割多少区间,使一段区间内的和的绝对值小于 m 。
Code
#include<cmath> #include<cstdio> #include<cstring> #include<iostream> using namespace std; int n,m; ]; ]; signed main(){ memset(f+,0x7f,sizeof f); scanf("%d%d",&n,&m); ;i<=n;i++){ scanf("%d",&x); ) cf[i]=cf[i-]+; ]-; } f[]=; ;i<=n;i++){ ;j<=i;j++){ ])<=m||abs(cf[i]-cf[j-])==i-j+) f[i]=min(f[i],f[j-]+); } } printf("%d",f[n]); ; }