CF1550B (Maximum Cost Deletion）

不妨设n为操作次数，序列长度为L：

显然Num的大小取决于n(操作次数）和b的正负

以b的正负分类讨论:

一、b>0时，n越大Num越大，n取最大操作次数L/1

二、b<0时，n越小Num越大，n取最小操作次数

? ? ? ? 问题来了，这个最小操作次数怎么算？可以发现01串交替，总段数=0串数+1串数，且0串数和1串数相差1。若先消去较小段数的串，最后一次性消去连上的段数较长的串。这种情况下有最小操作数。又因为01交替，找总段数直接转化成找交替的次数，以初始位置为1，找到一个交替点就+1，最后得到总段数，总操作次数为较小段数+最后一次

因为“/”向下取整，所以直接总段数/2就得到较小段数。

可以得到代码。

#include<iostream>
#include<cstring>
using namespace std;
int main()
{
	int N;
	cin >> N;
	while (N--) {
		int l, a, b, Num;
		string s;
		cin >> l >> a >> b >> s;
		if (b >= 0) {
			Num = l * a + l * b;
		}
		else {
			int cnt = 1;
			for (int i = 0; i < s.size()-1; i++) {
				if (s[i] != s[i + 1])
					cnt++;
			}
			Num = l * a + b * (cnt/2+1);
		}
		cout << Num << endl;
	}
	return 0;
}