upc bus 线性dp-白红宇的个人博客

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 奇怪的道路分形之城---改版

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

最新文章