CF1550B (Maximum Cost Deletion)

2023-12-21 06:56:56

不妨设n为操作次数,序列长度为L:

Num=\sum( l_i*a+b)=a*\sum l_i+n*b=a*L+n*b

显然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;
}

文章来源:https://blog.csdn.net/2302_79277225/article/details/135113071
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。