luogu P1564 膜拜

题目描述

神牛有很多…当然…每个同学都有自己衷心膜拜的神牛.

某学校有两位神牛，神牛甲和神牛乙。新入学的N 位同学们早已耳闻他们的神话。

所以，已经衷心地膜拜其中一位了。现在，老师要给他们分机房。但是，要么保证整个机房都是同一位神牛的膜拜者，或者两个神牛的膜拜者人数差不超过M。另外，现在N位同学排成一排，老师只会把连续一段的同学分进一个机房。老师想知道，至少需要多少个机房。

输入格式

输入文件第一行包括N 和M。

之后N 行，每行一个整数，1 表示神牛甲的崇拜者，2 表示神牛乙的崇拜者。

输出格式

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

.

直接O( n2）的动态规划

f[i]表示前i个人分的最少的机房

细节请看代码

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int N=2515;
int f[N],s1[N],s2[N];
signed main(){
    int n,m;
    cin>>n>>m;
    for(int i=1,x;i<=n;i++){
        s1[i]=s1[i-1];//前缀和
        s2[i]=s2[i-1];
        scanf("%lld",&x);
        if(x==1)s1[i]++;
        else s2[i]++;
        f[i]=1e9;//初始化
        for(int j=0;j<i;j++)//判断是否满足条件
        if(s1[i]-s1[j]==0||s2[i]-s2[j]==0||abs(s1[i]-s1[j]-(s2[i]-s2[j]))<=m)
        f[i]=min(f[i],f[j]+1);//判断分一个机房更优，或不分更优
    }
    cout<<f[n]<<endl;
}

luogu P1564 膜拜

原文：https://www.cnblogs.com/naruto-mzx/p/11602091.html