线性DP——看球的巴士（C++）

M. 看球的巴士

内存限制：128 MiB　　　　　　时间限制：1000 ms

标准输入输出　　　　　　题目类型：传统　　　　　　评测方式：文本比较

题目描述

两个球队的支持者要一起坐车去看球，他们已经排成了一列。我们要让他们分乘若干辆巴士，同一辆巴士上的人必须在队伍中是连续的。为了在车上不起冲突，希望两队的支持者人数尽量相等，差至多是D。有一个例外，就是一辆车上的人全部都是一个球队的支持者。问要将这N个人全部送至球场，至少要几辆巴士。

输入格式

第一行是整数N和D，1<=N<=2500，1<=D<=N。

接下来的N行，按排队的顺序，描述每个人支持的球队，用H或J表示。

输出格式

至少要几辆巴士。

样例

样例输入

14 3
H
J
H
H
H
J
H
J
H
H
H
H
H
H

样例输出

2

思路

设dp[i]表示到第i个人时的最优解

如果j表示截止到前j个人（j>=11）

if(hi==0||ji==0||abs(hi-ji)<=d)-->可以被一个车装

动态转移方程

dp[i]=min(dp[i],dp[j-1]+1);

所以

贴上代码

#include<algorithm>
#include<cstring>
using namespace std;
char a[3000];
int n,d,dp[3000],hi,ji;
int main()
{
    cin>>n>>d;
    memset(dp,0x3f,sizeof(dp));
    dp[0]=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        for(int j=i;j>=1;j--)
        {
            if(a[j]=='H')hi++;
            if(a[j]=='J') ji++;
            if(hi==0||ji==0||abs(hi-ji)<=d)
            {
                dp[i]=min(dp[i],dp[j-1]+1);
            }
        }
        hi=0;
        ji=0;
    }
    cout<<dp[n];
　  return 0;
}