题解 - 括号序列

标题描述

白浅妹妹在玩打怪游戏，游戏共有 n个关卡，每通过一个关卡就会遇到一把武器，它的代号为ai，表示当你第ai次遇到代号为ai的武器时，才气够获得这把武器（代号雷同的武器可以认为是雷同的武器）。
现在有 m 次询问，每次指定一个关卡区间 [L,R]，在通过这些关卡之后（白浅妹妹是一个高手，以是这些关卡都能通过），白浅妹妹必要从获得的武器中选出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) 两种。
【数据限定】

分析

相邻的非配对括号不能同色，
设第1个括号和第x个括号匹配，则可以将 [1,n] 分为 [1,x] 和 [x + 1,n]两部分，只必要满足第x个括号和第 x + 1 个括号不同色即可，因为可以想到 区间dp
f[l][r][x][y] 表示第l个括号涂x色，第r个括号涂y色时，区间[l,r]的最大代价 （此中用0，1，2分别代表不染色、染白色、染玄色）
最终结果即为 max({f[1][n][0][0],f[1][n][0][1],f[1][n][0][2],f[1][n][1][0],f[1][n][1][1],f[1][n][1][2],f[1][n][2][0],f[1][n][2][1],f[1][n][2][2]})
如果l和r配对，可以转移到 [l + 1,r - 1] ，此时x==y，故摆列x == 0，1，2即可

如果l和r不配对，找到l配对的右括号k，则可以转移到 [l,k] 和 [k + 1,r] ，摆列x和y的组合即可（9种）

此外，我们可以直接预处置处罚出每个左括号所配对的右括号，通过栈实现
代码

1. #pragma GCC optimize(2)
2.   
3. #include<bits/stdc++.h>
4.    
5. using namespace std;
6.    
7. typedef long long LL;
8.    
9. const int N = 1000 + 10,M = 1e6 + 10;
11. int n,a,b;
12. string s;
13. int R[N];
14. int f[N][N][3][3];
16. int main(){
17.     ios::sync_with_stdio(false);
18.     cin.tie(0),cout.tie(0);
20.     cin >> n >> a >> b >> s;
21.      
22.     s = " " + s;
24.     stack<int> stk;
25.     for(int i = 1;i <= n;i++){
26.         if(s[i] == '(') stk.push(i);
27.         else{
28.             R[stk.top()] = i;
29.             stk.pop();
30.         }
31.     }
33.     for(int len = 2;len <= n;len += 2)
34.         for(int i = 1;i + len - 1 <= n;i++){
35.             int l = i,r = i + len - 1;
37.             if(s[l] == ')' || s[r] == '(') continue;
39.             if(len == 2){
40.                 f[l][r][0][0] = 0;
41.                 f[l][r][1][1] = a;
42.                 f[l][r][2][2] = b;
43.             }else if(R[l] == r){
44.                 f[l][r][0][0] = max({f[l + 1][r - 1][1][1],f[l + 1][r - 1][1][2],f[l + 1][r - 1][2][1],f[l + 1][r - 1][2][2]});
45.                 f[l][r][1][1] = max({f[l + 1][r - 1][0][0],f[l + 1][r - 1][0][2],f[l + 1][r - 1][2][0],f[l + 1][r - 1][2][2]}) + a;
46.                 f[l][r][2][2] = max({f[l + 1][r - 1][0][0],f[l + 1][r - 1][0][1],f[l + 1][r - 1][1][0],f[l + 1][r - 1][1][1]}) + b;
47.             }else{
48.                 int k = R[l];
49.                 f[l][r][0][0] = max(f[l][k][0][0] + f[k + 1][r][1][0],f[l][k][0][0] + f[k + 1][r][2][0]);
50.                 f[l][r][0][1] = max(f[l][k][0][0] + f[k + 1][r][1][1],f[l][k][0][0] + f[k + 1][r][2][1]);
51.                 f[l][r][0][2] = max(f[l][k][0][0] + f[k + 1][r][1][2],f[l][k][0][0] + f[k + 1][r][2][2]);
52.                 f[l][r][1][0] = max(f[l][k][1][1] + f[k + 1][r][0][0],f[l][k][1][1] + f[k + 1][r][2][0]);
53.                 f[l][r][1][1] = max(f[l][k][1][1] + f[k + 1][r][0][1],f[l][k][1][1] + f[k + 1][r][2][1]);
54.                 f[l][r][1][2] = max(f[l][k][1][1] + f[k + 1][r][0][2],f[l][k][1][1] + f[k + 1][r][2][2]);
55.                 f[l][r][2][0] = max(f[l][k][2][2] + f[k + 1][r][0][0],f[l][k][2][2] + f[k + 1][r][1][0]);
56.                 f[l][r][2][1] = max(f[l][k][2][2] + f[k + 1][r][0][1],f[l][k][2][2] + f[k + 1][r][1][1]);
57.                 f[l][r][2][2] = max(f[l][k][2][2] + f[k + 1][r][0][2],f[l][k][2][2] + f[k + 1][r][1][2]);
58.             }
59.         }
61.     cout << max({f[1][n][0][0],f[1][n][0][1],f[1][n][0][2],f[1][n][1][0],f[1][n][1][1],f[1][n][1][2],f[1][n][2][0],f[1][n][2][1],f[1][n][2][2]});
63.     return 0;
64. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。