看球的巴士——线性dp

【题目描述】

两个球队的支持者要一起坐车去看球，他们已经排成了一列。我们要让他们分乘若干辆巴士，同一辆巴士上的人必须在队伍中是连续的。为了在车上不起冲突，希望两队的支持者人数尽量相等，差至多是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，but  ……这就很尴尬了

•  还是逐步分析吧，首先从最初情况入手，i个人，至多i个大巴（显然不会用这么多，但是要在此基础上处理），那么f[i]要怎么处理呢
• 在前i个人中，不难发现可以乘坐大巴的情况有可能有很多，所有我们从1~j（j<=i）依次跑一边，看能否将其放在一个大巴里，如果可以，那（j，i）区的人用一个大巴就可以装下了，而（1，j）区间内已经处理好，直接拿过来就可以了，推出转移方程为 f[i] = max(f[i],f[j]+1)，转移方程想好了，接下来的就比较简单了

• 既然是对区间进行处理，那么我们记录数据就选择用前缀和数组，用前缀和数组H[i]记录H方的人数，J[i]数组记录J方的人数，我们只需找出哪些区间里的人可以乘坐一辆大巴就行了，分为两种：

　　　　　1.整个大巴上都是同一个球队的球迷，那显然(j,i)区间的长度，就是H数组或J数组在这个区间内的个数：

　　　　　  合法条件为：H[j] - H[i-1] == j-i+1 || J[j] - J[i-1] == j-i+1 

　　　　　2.大巴上有两个球队的球迷，那在(i,j)区间内两个数组的差值就要小于等于D：

　　　　　  合法条件为：abs(J[j]-J[i-1]-(H[j]-H[i-1])) <= d

细节见代码注释

【代码】

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 2500+10;
int n,d;
int f[N],H[N],J[N],v[N][N];
int main(){
    scanf("%d%d",&n,&d);
    for(int i = 1;i <= n;i++){
        char c;scanf(" %c",&c); //注意加空格！！！
        if(c=='H'){   //前缀和数组依次赋值
            H[i] = H[i-1]+1;   
            J[i] = J[i-1];
        }
        else{
            J[i] = J[i-1]+1;
            H[i] = H[i-1];
        }
        f[i] = i;
    }
    for(int i = 1;i <= n;i++){//找出可以乘坐同一辆大巴的区间
        for(int j = i;j <= n;j++){ //关键点，注意下标不要弄错，减去的是H[i-1]或J[i-1],差值减去的也同样是i-1，才能代表（i,j）区间
            if(H[j] - H[i-1] == j-i+1 || J[j] - J[i-1] == j-i+1 || abs(J[j]-J[i-1]-(H[j]-H[i-1])) <= d){
                v[i][j] = 1;
            }
        }
    }
    for(int i = 1;i <= n;i++){ //dp环节
        for(int j= 1;j <= i;j++){
            if(v[j][i])f[i] = min(f[i],f[j-1]+1);//这是减去j-1，查错查了半天
        }
    }
    printf("%d",f[n]);
    return 0;
}