upc bus 线性dp
发布日期:2021-09-25 23:57:38 浏览次数:0 分类:技术文章

本文共 1399 字,大约阅读时间需要 4 分钟。

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
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define X first#define Y secondusing namespace std;typedef long long LL;typedef pair
               
                 PII;const int N=2500,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-6;int n,d;int a,b;int f[N];string s;int prh[N],prj[N];bool st[N][N]; int main(){    //
                
ios::sync_with_stdio(false);//
cin.tie(0);
cin>>n>>d>>s;
int l=s.length();
for(int i=0;i
{    
f[i+1]=i+1;
if(s[i]=='H') prh[i+1]=prh[i]+1,prj[i+1]=prj[i];
else prh[i+1]=prh[i],prj[i+1]=prj[i]+1;
}
for(int i=1;i<=n;i++)//预处理i到j一辆够不够 
{    
for(int j=i;j<=n;j++)
{    
int a=prh[j]-prh[i-1],b=prj[j]-prj[i-1],c=j-i+1;
if(a==c||b==c||abs(a-b)<=d)
st[i][j]=true;
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
if(st[j][i]) 
f[i]=min(f[i],f[j-1]+1);
cout< <
return 0;}

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

上一篇:斐波那契数列 线性dp
下一篇:upc 奇怪的道路 分形之城---改版

发表评论

最新留言

不错!
[***.235.140.84]2022年08月08日 06时23分45秒