题解 - 括号序列
标题描述白浅妹妹在玩打怪游戏，游戏共有 n个关卡，每通过一个关卡就会遇到一把武器，它的代号为ai，表示当你第ai次遇到代号为ai的武器时，才气够获得这把武器（代号雷同的武器可以认为是雷同的武器）。
现在有 m 次询问，每次指定一个关卡区间 ，在通过这些关卡之后（白浅妹妹是一个高手，以是这些关卡都能通过），白浅妹妹必要从获得的武器中选出ki个（包管 ki≤ 4 ）来与怪物对决，你必要输出你有多少种组合方案。
输入
第一行输入一个整数 n 表示关卡的数量。
第二行输入n个整数 ai（1 ≤ ai ≤ 109）表示第 i 个关卡遇到的武器的代号（包管任意两个武器的代号互不雷同）。
第三行输入一个整数 m 表示挑战次数。
接下来的 m行，每行三个正整数Li, Ri, ki (1 ≤ Li ≤ Ri ≤ n, 1 ≤ ki ≤ 4) ，表示必要通过的关卡区间。
输出
输出m行，每行一个整数，表示该次挑战武器组合方案数量。
样例
样例输入
7
1 3 7 2 3 7 2
4
1 1 1
2 5 4
4 7 1
1 7 1
样例输出
1
0
1
2
提示
【样例解释】
对于第一个询问，获得的武器为 1 ，选出一把武器的方案为 (1)
对于第二个询问，没有获得的武器。
对于第三个询问，获得的武器为 2，选出一把武器的方案为 (2)
对于第四个询问，获得的武器为 1,2，选出一把武器的方案为 (1), (2) 两种。
【数据限定】
https://i-blog.csdnimg.cn/direct/da9dfd9c7dd24d1aa04688a523b44fb1.png
分析
相邻的非配对括号不能同色，
设第1个括号和第x个括号匹配，则可以将 分为 和 两部分，只必要满足第x个括号和第 x + 1 个括号不同色即可，因为可以想到 区间dp
f 表示第l个括号涂x色，第r个括号涂y色时，区间的最大代价 （此中用0，1，2分别代表不染色、染白色、染玄色）
最终结果即为 max({f,f,f,f,f,f,f,f,f})
如果l和r配对，可以转移到 ，此时x==y，故摆列x == 0，1，2即可
https://i-blog.csdnimg.cn/direct/69e29ed222114201a076343a6f77b57e.png
如果l和r不配对，找到l配对的右括号k，则可以转移到 和 ，摆列x和y的组合即可（9种）
https://i-blog.csdnimg.cn/direct/c4f01799c932423ab8fa9be0e075bf76.png
此外，我们可以直接预处置处罚出每个左括号所配对的右括号，通过栈实现
代码
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1000 + 10,M = 1e6 + 10;
int n,a,b;
string s;
int R;
int f;
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> n >> a >> b >> s;
s = " " + s;
stack<int> stk;
for(int i = 1;i <= n;i++){
if(s == '(') stk.push(i);
else{
R = i;
stk.pop();
}
}
for(int len = 2;len <= n;len += 2)
for(int i = 1;i + len - 1 <= n;i++){
int l = i,r = i + len - 1;
if(s == ')' || s == '(') continue;
if(len == 2){
f = 0;
f = a;
f = b;
}else if(R == r){
f = max({f,f,f,f});
f = max({f,f,f,f}) + a;
f = max({f,f,f,f}) + b;
}else{
int k = R;
f = max(f + f,f + f);
f = max(f + f,f + f);
f = max(f + f,f + f);
f = max(f + f,f + f);
f = max(f + f,f + f);
f = max(f + f,f + f);
f = max(f + f,f + f);
f = max(f + f,f + f);
f = max(f + f,f + f);
}
}
cout << max({f,f,f,f,f,f,f,f,f});
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]