神牛有很多...当然...每个同学都有自己衷心膜拜的神牛.
某学校有两位神牛，神牛甲和神牛乙。新入学的 nn 位同学们早已耳闻他们的神话。
所以，已经衷心地膜拜其中一位了。现在，老师要给他们分机房。但是，要么保证整个机房都是同一位神牛的膜拜者，或者两个神牛的膜拜者人数差不超过 mm。另外，现在 nn 位同学排成一排，老师只会把连续一段的同学分进一个机房。老师想知道，至少需要多少个机房。
输入文件第一行包含两个整数 nn 和 mm。
第 22 到第 (n + 1)(n+1) 行，每行一个非 11 即 22 的整数，第 (i + 1)(i+1) 行的整数表示第 ii 个同学崇拜的对象，11 表示甲，22 表示乙。
输出一个整数，表示最小需要机房的数量。
把所有的2换成-1，问题就转换成了，使每个机房里的元素权值的绝对值小于等于m。
简单线性DP做一下即可。
#include<bits/stdc++.h> using namespace std; const int maxn=5005; int dp[maxn]; int a[maxn]; int c[maxn]; int n,m; 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++) if (a[i]==2) a[i]-=3; for (int i=1;i<=n;i++) c[i]=c[i-1]+a[i]; for (int i=1;i<=n;i++) dp[i]=1e9; for (int i=1;i<=n;i++) { for (int j=i-1;j>=0;j--) { if (abs(c[i]-c[j])<=m||c[i]-c[j]==i-j||c[i]-c[j]==j-i) { dp[i]=min(dp[i],dp[j]+1); } } //printf("%d\n",dp[i]); } printf("%d\n",dp[n]); }
原文：https://www.cnblogs.com/zhanglichen/p/13462292.html