标签：13 cost string ml 37 cnt CF1837B

Comparison String

题面翻译

给你一个长度为 $n$ 的由 < 和 > 构成的字符串 $s$，如果一个数列 $a$ 能满足将字符串 $s$ 的所有大于号和小于号按顺序填入后满足大小关系，则 $a$ 数列和 $s$ 字符串是“相容的”。
定义一个数列的花费是这个数列中不同元素的数量。
已知字符串 $s$，让你求出与 $s$ 相容的所有数列中花费最小的数列的花费。

题目描述

You are given a string $ s $ of length $ n $ , where each character is either < or >.

An array $ a $ consisting of $ n+1 $ elements is compatible with the string $ s $ if, for every $ i $ from $ 1 $ to $ n $ , the character $ s_i $ represents the result of comparing $ a_i $ and $ a_{i+1} $ , i. e.:

$ s_i $ is < if and only if $ a_i < a_{i+1} $ ;
$ s_i $ is > if and only if $ a_i > a_{i+1} $ .

For example, the array $ [1, 2, 5, 4, 2] $ is compatible with the string <<>>. There are other arrays with are compatible with that string, for example, $ [13, 37, 42, 37, 13] $ .

The cost of the array is the number of different elements in it. For example, the cost of $ [1, 2, 5, 4, 2] $ is $ 4 $ ; the cost of $ [13, 37, 42, 37, 13] $ is $ 3 $ .

You have to calculate the minimum cost among all arrays which are compatible with the given string $ s $ .

输入格式

The first line contains one integer $ t $ ( $ 1 \le t \le 500 $ ) — the number of test cases.

Each test case consists of two lines:

the first line contains one integer $ n $ ( $ 1 \le n \le 100 $ );
the second line contains the string $ s $ , consisting of $ n $ characters. Each character of $ s $ is either < or >.

输出格式

For each test case, print one integer — the minimum cost among all arrays which are compatible with the given string $ s $ .

样例 #1

样例输入 #1

4
4
<<>>
4

<<
5

样例输出 #1

3
3
6
2

提示

In the first test case of the example, the array can be $ [13, 37, 42, 37, 13] $ .

In the second test case of the example, the array can be $ [42, 37, 13, 37, 42] $ .

分析

通过分析所给样例可以得出，答案是最长的连续出现的相同符号的个数 + 1，很简单很不讲道理，或许这就是贪心吧

代码

#include <iostream>
using namespace std;
char str[110];
int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		int n;
		scanf("%d%s", &n, str);
		char last = 'a';
		int cnt = 1, ml = 0;
		for (int i = 0; i < n; i++)
		{
			if (str[i] != last)
			{
				ml = max(ml, cnt);
				last = str[i];
				cnt = 1;
			}
			else
				cnt++;
		}
		ml = max(ml, cnt);
		printf("%d\n", ml + 1);
	}
}

标签：13,cost,string,ml,37,cnt,CF1837B
From： https://www.cnblogs.com/beishangeyu/p/17700991.html

CF1837B