CF1550B Maximum Cost Deletion(分段比较)

简介: CF1550B Maximum Cost Deletion(分段比较)

You are given a string ss of length n  consisting only of the characters 0 and 1.


You perform the following operation until the string becomes empty: choose some consecutive substring of equal characters, erase it from the string and glue the remaining two parts together (any of them can be empty) in the same order. For example, if you erase the substring 111 from the string 111110, you will get the string 110. When you delete a substring of length ll, you get a⋅l+b  points.


Your task is to calculate the maximum number of points that you can score in total, if you have to make the given string empty.


Input


The first line contains a single integer tt (1≤t≤2000 ) — the number of testcases.


The first line of each testcase contains three integers n , a  and b ( 1≤n≤100;−100≤a,b≤100) — the length of the string s and the parameters a  and b .


The second line contains the string ss. The string ss consists only of the characters 0 and 1.


Output


For each testcase, print a single integer — the maximum number of points that you can score.


Example


Input

1. 3
2. 3 2 0
3. 000
4. 5 -2 5
5. 11001
6. 6 1 -4
7. 100111


Output

1. 6
2. 15
3. -2


大意



有一个01字符串,每次可以删去一段连续的0或1,删除一段长为  l 的字符串可得到 a∗l+b 分,求最大分数。


由于字符串最后必须变为空串,显然  a∗l 合并同类项后为  a∗n 故只需让 b  最大化即可。

由于  +b 的次数与删除次数有关所以分类讨论


  • 当  b≥0 时,取的越多越好,操作 n 次
  • 当  b<0 时,取得越少越好,可以证明,先全部删去连续区间数量较少的,再一下把另一个全删了,操作次数最少


举个例子 10011001

最优解: 10011001⇒1111⇒ 空串

错解    :10011001⇒111001⇒001⇒1⇒ 空串

可见每个0串还是得单独删去,而1串删除的操作分为两步,故不如最优解。


具体实现看代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
  int t;
  cin>>t;
  while(t--)
  {
      int c0=0,c1=0,ans=0; //chush
    int n,a,b;
    string s;
    cin>>n>>a>>b;
    cin>>s;
    if(b<0)
    {
      for(int i=0;i<n;i++)
      if(s[i]=='0')
      {
        int p=i;
        while(s[p]=='0')
        p++;
        i=p-1;
        c0++;
      }
     for(int i=0;i<n;i++)
      if(s[i]=='1')
      {
        int p=i;
        while(s[p]=='1')
        p++;
        i=p-1;
        c1++;
      }           
    ans=a*n+min(c1,c0)*b+b;
    }
    else
    ans=b*n+a*n;  
    cout<<ans<<endl;  
   } 
 } 



相关文章
|
6月前
|
存储 算法 Java
Minimum Transport Cost(ZOJ - 1456)
Minimum Transport Cost(ZOJ - 1456)
|
存储 Linux Windows
ChIP-seq 分析:Call Peak(8)
ChIP-seq 分析:Call Peak(8)
315 0
|
Java 应用服务中间件
The field file exceeds its maximum permitted size of 1048576 bytes.
The field file exceeds its maximum permitted size of 1048576 bytes.
|
人工智能
Tree with Maximum Cost---CF1092F 树上DP
You are given a tree consisting exactly of n vertices. Tree is a connected undirected graph with n−1 edges. Each vertex v of this tree has a value av assigned to it. Let dist(x,y) be the distance between the vertices x and y.
141 0
Tree with Maximum Cost---CF1092F 树上DP
|
前端开发 Java 关系型数据库
记录:The field files exceeds its maximum permitted size of 1048576 bytes...【亲测有效】
记录:The field files exceeds its maximum permitted size of 1048576 bytes...【亲测有效】
1132 0
|
监控
【分析】segments的version_map_memory指标具体表示什么?
ES有很多的监控指标,其中有一些指标官方解释的实在模糊。 比如version_map_memory:(byte units) Total amount of memory used by all version maps across all shards assigned to selected nodes.
269 0
【分析】segments的version_map_memory指标具体表示什么?
PAT (Advanced Level) Practice - 1145 Hashing - Average Search Time(25 分)
PAT (Advanced Level) Practice - 1145 Hashing - Average Search Time(25 分)
119 0
|
供应链
PAT (Advanced Level) Practice - 1079 Total Sales of Supply Chain(25 分)
PAT (Advanced Level) Practice - 1079 Total Sales of Supply Chain(25 分)
139 0
【1079】Total Sales of Supply Chain (25 分)
【1079】Total Sales of Supply Chain (25 分) 【1079】Total Sales of Supply Chain (25 分)
117 0