#P17794. Two Characters, Two Colors
Two Characters, Two Colors
CF1895G Two Characters, Two Colors
题目描述
给定一个只包含字符 和/或 的字符串。你需要将该字符串的每个字符涂成红色或蓝色。
如果你将第 个字符涂成红色,你可以获得 个金币。如果你将其涂成蓝色,你可以获得 个金币。
涂色结束后,你将所有蓝色字符从字符串中移除,并统计剩余字符串中的逆序对数量(即左边字符为 ,右边字符为 的字符对的数量)。对于每一个逆序对,你需要支付 个金币。
你最多能获得多少金币?
输入格式
输入的第一行为一个整数 (),表示测试用例的数量。
每个测试用例包含四行:
- 第一行为一个整数 (),表示字符串的长度;
- 第二行为一个长度为 的字符串 ,其中每个字符为 或 ;
- 第三行为 个整数 ();
- 第四行为 个整数 ()。
额外限制:所有测试用例中 的总和不超过 。
输出格式
对于每个测试用例,输出一个整数,表示你最多能获得的金币数。
输入输出样例 #1
输入 #1
4
7
0100010
6 6 6 7 7 6 6
3 3 5 4 7 6 7
5
10111
9 8 5 7 5
4 4 7 8 4
10
0100000000
7 7 6 5 2 2 5 3 8 3
8 6 9 6 6 8 9 7 7 9
8
01010000
8 7 7 7 8 7 7 8
4 4 4 2 1 4 4 4
输出 #1
43
36
76
52
说明/提示
示例中各测试用例的解释(蓝色字符已下划线,红色字符未下划线):
- ;
- ;
- ;
- 。