首页 > 代码库 > 看球的巴士 ballbus
看球的巴士 ballbus
看球的巴士 ballbus
【题目描述】：
两个球队的支持者要一起坐车去看球，他们已经排成了一列。我们要让他们分乘若干辆巴士，同一辆巴士上的人必须在队伍中是连续的。为了在车上不起冲突，希望两队的支持者人数尽量相等，差至多是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 |
【数据范围及描述】：
内存限制51200K
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <algorithm> 5 using namespace std; 6 7 const int maxn=2505; 8 int N,D; 9 int F[maxn];10 11 int _min(int a,int b)12 {13 return a<b?a:b;14 }15 16 int _abs(int x)17 {18 return x<0?-x:x;19 }20 21 int main()22 {23 scanf("%d %d\n",&N,&D);24 memset(F,0x7f7f7f7f,sizeof(F));25 char ch[maxn];26 F[0]=0;27 for(int i=1;i<=N;i++)28 {29 scanf("%c\n",&ch[i]);30 int H,J;31 H=J=0;32 for(int j=i;j>=1;j--)33 {34 if(ch[j]==‘H‘) H++;35 else J++;36 if(H==0||J==0||_abs(H-J)<=D) F[i]=_min(F[i],F[j-1]+1);37 }38 }39 printf("%d",F[N]);40 return 0;41 }42 43 44 45 46 47
看球的巴士 ballbus
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。