P1564 膜拜

    • 462通过
    • 1.1K提交
  • 题目提供者 JOHNKRAM
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

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

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

    输入输出格式

    输入格式:

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

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

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    5 1
    2
    2
    1
    2
    2
    输出样例#1: 复制
    2

    说明

    对于30%的数据,有1 ≤ N ,M≤ 50;

    对于100%的数据,有1 ≤ N,M ≤ 2500。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。