2 seconds

256 megabytes

standard input

standard output

 #include<bits/stdc++.h>

 using namespace std;

 const int amn=2e5+;

 long long m[amn],jg[amn];

 int main(){

     long long T,n,a,b,st,ed,tp=;long long ans;char in;

     ios::sync_with_stdio();

     cin>>T;

     while(T--){

         tp=;

         cin>>n>>a>>b;

         st=-;ans=ed=;

         for(int i=;i<n;i++){cin>>in;if(in=='')m[i]=;else m[i]=;}m[n]=;

         for(int i=;i<n;i++){

             if(m[i]==){

                 if(st==-)st=i-;

                 if(i>){

                         if(m[i-]==)m[i-]=;

                         else m[i-]=;      ///如果这个管道既要上升又要下降,则必须建高管道

                 }

                 if(i+<n){

                         if(m[i+]==){m[i+]=;ed=i+;}

                         else m[i+]=;      ///如果这个管道既要上升又要下降,则必须建高管道(其实这里不用判断,因为前面还没判断过,不可能有2,只可能时1或0

                 }

             }

         }

         for(int i=;i<n;i++)

             if(m[i]==||m[i]==)jg[tp++]=i;

         for(int i=;i<tp;i++){      ///注意位置i从0开始哦!    注意题中规定第1个管道必定是低管道或上升管道,最后一个必定是下降管道或低管道,下面的每个格子代价计算的是格子左边柱子的代价和格子管道的代价,低管道a+b,高管道a+2*b,上升管道2*a+b,下降管道2*a+2*b

             if(i==)        ///在第一次访问时i为偶数是上升管道,但前面没有下降管道,故要算建低管道的代价和上升管道的代价

                 ans+=jg[i]*(a+b)+*a+b;

             else if(i==tp-)    ///在最后一次访问时i为奇数时下降管道,但后面没有上升管道了,故要算建下降管道和低管道的代价

                 ans+=(n--jg[i])*(a+b)+*a+*b;

             if(i!=tp-){    ///如果在中间

                 if(i&){        ///由于管道有升就有降且必定先升再降,而且才0开始存上升下降位置,所以偶数位存上升管道,奇数位置存下降管道

                     long long have=jg[i+]-jg[i]-;     ///have计算从下降管道到上升管道之间有多少个高度低管道注意这里要开long long,不然会溢出

                     if(*a-b>=have*b)       ///在可以先下降在上升的管道区域要判断是否这样建还是不下降而是继续全建高管道,选一个代价小的建,用2*a-b>=have*b这个公式判断,它是这样推出来的,设1类为这一段建下降管道,低管道,上升管道,2类为这一段全建高管道,1类的代价为(4*a+3*b+have*(a+b)),2类代价为(have+2)*(a+2*b),可见1类和2类在have不同时代价不同,所以可以做差来比较它们的大小,即推出此公式

                         ans+=(have+)*(a+*b);

                     else

                         ans+=(*a+*b+have*(a+b));

                 }

                 else    ///如果现在这个是上升管道则只算高管道有多少,因为第一个上升管道代价第一次时已经算过了,而中间碰到下降管道时计算代价是下降管道+低管道+上升管道

                     ans+=(jg[i+]-jg[i]-)*(a+*b);

             }

         }

         if(tp==)       ///如果没有上升和下降的管道则全建低管道

             ans+=n*(a+b);

         printf("%lld\n",ans+b); ///最后一个管道的右边柱子的代价要加上

     }

 }

 /**

 给一个长度为n的01串,和建单位长度的管道的代价a和单位长度的柱子b的代价,有4种柱子,低管道代价为a+b,高管道代价为a+2*b,上升管道代价为2*a+b,下降管道代价为2*a+2*b,01串中1代表要建高管道,一段高管道前要建上升管道,后要建下降管道,如果一个地方既要上升管道有要下降管道,则那个地方必须为高管道,问建这个区域管道和柱子的最小代价

 读入01串后给管道分类,低管道为0,高管道为1,上升管道为2,下降管道为3,如果这个管道既要上升又要下降,则必须建高管道,再提取出上升管道和下降管道(这里设i从0开始),注意到只能是中间的某些下降管道到下一个上升管道这段看要不要换成全部都是高管道来比较代价,

 注意题中规定第1个管道必定是低管道或上升管道,最后一个必定是下降管道或低管道,下面的每个格子代价计算的是格子左边柱子的代价和格子管道的代价,

 在第一次访问时i为偶数是上升管道,但前面没有下降管道,故要算建低管道的代价和上升管道的代价,在最后一次访问时i为奇数时下降管道,但后面没有上升管道了,故要算建下降管道和低管道的代价,

 如果在中间,由于管道有升就有降且必定先升再降,而且才0开始存上升下降位置,所以偶数位存上升管道,奇数位置存下降管道,

 如果现在这个管道是下降管道,have计算从下降管道到上升管道之间有多少个高度低管道注意这里要开long long,不然会溢出,在可以先下降在上升的管道区域要判断是否这样建还是不下降而是继续全建高管道,选一个代价小的建,用2*a-b>=have*b这个公式判断,它是这样推出来的,设1类为这一段建下降管道,低管道,上升管道,2类为这一段全建高管道,1类的代价为(4*a+3*b+have*(a+b)),2类代价为(have+2)*(a+2*b),可见1类和2类在have不同时代价不同,所以可以做差来比较它们的大小,即推出此公式

 如果现在这个是上升管道则只算高管道有多少,因为第一个上升管道代价第一次时已经算过了,而中间碰到下降管道时计算代价是下降管道+低管道+上升管道.

 还要判断如果没有上升和下降的管道则全建低管道,

 输出答案时最后一个管道的右边柱子的代价要加上

 **/