T202891 团队练习

与一般dp的变化

前缀和：段差

：前人宿舍数

代码

#include
using namespace std;
int n,s[100001],f[100001],v,m;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		cin>>v;
		s[i]=s[i-1];
		if(v==1)
			++s[i];
		else
			--s[i];
		f[i]=1e6;
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=i;++j)
			if(abs(s[i]-s[j-1])==i-j+1||abs(s[i]-s[j-1])<=m)
				f[i]=min(f[i],f[j-1]);
		++f[i];
	}
	cout<