【动态规划】mr354-坐车看球

【题目大意】

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

【思路】

记录下到第i个人为止，支持两队的人的个数，接下来预处理[i,j]之间的人能否坐在一辆车上，如果它们能坐在一辆车上，必定满足以下三个条件中的一个：

(1)[i,j]均支持H队，即H[j]-H[i-1]==j-i+1;

(2)[i,j]均支持J队，即J[j]-J[i-1]==j-i+1;

(3)[i,j]支持H队和J队的人数差小于等于D，即|( H[j]-H[i-1])-( J[j]-J[i-1])|≤D。

预处理结束之后，依次判断区间[i,j]，car[j]表示到第j个人为止最少需要多少辆车。如果[i,j]区间内的人能公用一辆车，则car[j]=min(car[j],car[i-1]+1)。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 using namespace std;
 5 const int MAXN=2500+50;
 6 int n,d;
 7 int can[MAXN][MAXN]; 
 8 int H[MAXN],J[MAXN];
 9 int car[MAXN];
10 
11 int main()
12 {
13     freopen("mr354.in0","r",stdin);
14     freopen("mr354.ou0","w",stdout);
15     scanf("%d%d",&n,&d);
16     memset(H,0,sizeof(H));
17     memset(J,0,sizeof(J));
18     memset(can,0,sizeof(can));
19     for (int i=1;i<=n;i++)
20     {
21         getchar();
22         char c;
23         scanf("%c",&c);
24         H[i]=H[i-1];
25         J[i]=J[i-1];
26         if (c=='H') H[i]++; else J[i]++;
27         car[i]=i;
28     }
29 
30     
31     for (int i=1;i<=n;i++)
32         for (int j=i;j<=n;j++)
33             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)
34                 can[i][j]=1;
35                 
36     for (int i=1;i<=n;i++)
37         for (int j=1;j<=i;j++)
38             if (can[j][i])
39                 car[i]=min(car[i],car[j-1]+1);
40                 
41     cout<<car[n]<<endl;
42     return 0;
43 }