本文共 1032 字，大约阅读时间需要 3 分钟。

bus

时间限制: 1 Sec 内存限制: 128 MB

题目描述

两个球队的支持者要一起坐车去看球，他们已经排成了一列。我们要让他们分乘若干辆巴士，同一辆巴士上的人必须在队伍中是连续的。为了在车上不起冲突，希望两队的支持者人数尽量相等，差至多是D。有一个例外，就是一辆车上的人全部都是一个球队的支持者。问要将这N个人全部送至球场，至少要几辆巴士。 输入 第一行是整数N和D。 接下来一行，按排队的顺序，描述每个人支持的球队，用H或J表示。该行没有任何多余的字符。 输出 一个整数，表示要多少巴士。 样例输入 Copy 14 3 HJHHHJHJHHHHHH 样例输出 Copy 2 提示 对于100%的数据：N,D≤2500，数据有合理的梯度。

状态表示：f[ i ] 表示到第 i 个人需要的最少巴士数量。

状态转移：f[ i ] = min(f[ i ] , f[ j - 1 ] + 1) 转移的条件就是 ( i , j ) 这个区间只需要一辆巴士，那么就可以考虑预处理出每一个区间是否一辆巴士就可以解决。 尝试枚举每个区间，当全是一队人或者两队之差 <= d 的时候即可。 为了优化预处理区间的时候需要每一段区间中两队的人数，可以预处理出前缀和。

好吧，思路和代码完全是反着来的。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
      
     
    
   

转载地址：https://blog.csdn.net/DaNIelLAk/article/details/105883029 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！