$250$ $pits$

T3 武器选择

solution

首先读题 $n <= 10^5$ 暴力会超 , 考虑优化

1. 预处理出每个武器出现了多少次 , 如果一个武器出现的次数比武器的编号少的话就说明武器不可能被选 , 应有 $sqrt(n)$ 个武器被选

2. 用前缀和处理出 $(l , r)$ 区间内有多少个武器数 , 具体如下 :

   前缀和 $f[j][g[i]] = f[j - 1][g[i]] = f[j - 1][g[i]] + (a[j] == g[i])$

   处理 $(l , r)$ 区间和 $f[r][g[i]] - f[l - 1][g[i]]$

   其中 , $f[l][r]$ 是 $(l , r)$ 区间和 , $g[i]$ 是能被选的武器号

3. 预处理组合数

4. 统计答案 , 具体地 : 若区间和 $(l , r)$ 大于武器编号的话 , $ans ++$ , 最后输出 $c(k , ans)$ , $c$ 是组合数 不会LaTex

code

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

long long n , m , a[N] , to[N];
int f[N][505];
vector<int> g;

long long c(long a , long b){
	if(a > b) return 0;
	if(a == b) return 1;
	
	int s = 1 , d = 1;
	for(int i = 2 ; i <= a ; i ++) s *= i;
	for(int i = b ; i >= b - a + 1 ; i --) d *= i;
	
	return d / s;
}

void solve(int l , int r , int k){
	int sum = 0;
	for(int i = 0 ; i < g.size() ; i ++){
		if(f[r][g[i]] - f[l - 1][g[i]] >= g[i]) sum ++;
	}
	
	cout << c(k , sum) << endl;
}

signed main(){
	freopen("wq.in" , "r" , stdin);
	freopen("wq.out" , "w" , stdout);
	
	cin >> n;
	for(int i = 1 ; i <= n ; i ++){
		cin >> a[i];
		if(a[i] < 1e5) to[a[i]] ++;
	}
	for(int i = 1 ; i < 1e5 ; i ++){
		if(to[i] >= i) g.push_back(i);
	}
	for(int i = 0 ; i < g.size() ; i ++){
		for(int j = 1 ; j <= n ; j ++){
			f[j][g[i]] = f[j - 1][g[i]];
			if(a[j] == g[i]) f[j][g[i]] += 1;
		}
	}
	cin >> m;
	while(m --){
		int l , r , k;
		cin >> l >> r >> k;
		solve(l , r , k);
	}
	return 0;
}

T4 括号序列

solution

这是一道 $dp$ 题目，思路如下

0. 预处理，用两个数组 $L[] , R[]$ 标记括号对应的另一个括号的位置，用一个栈来遍历
1. 状态：$dp_i,_j,_x,_y$ 表示起始是 $i$ 颜色为 $x$ , 结尾是 $j$ 颜色为 $y$ 的染色最大值
2. 答案：$ans = dp_1,_n,_i,_j$

记忆化搜索思路

1. 当前区间为合法的序列

   如果 $l + 1 == r$ 直接返回 $cost[x]$

   否者枚举颜色，当颜色不为当前颜色时，转移 $mx = max(mx , v + dfs(l + 1 , r - 1 , i , j))$

2. 当前区间为不合法的序列

   枚举颜色，当首尾颜色不一样时，枚举间断点 $mx = max(mx , dfs(l , R[l] , x , i) + dfs(R[l] + 1 , r , j , y))$

3. 记忆化 $dp_l,_r,_x,_y = mx$

动态规划思路

0. 确立枚举循序： 先枚举长度，再根据长度来枚举左右端点

1. 当前区间为合法的序列 分别考虑 只有一个括号，括号内匹配和不匹配三种情况

2. 当前区间为不合法的序列 同 $(1)$ 一样，分类讨论

code

记忆化搜索

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e3 + 5;

int n , cost[3] , dp[N][N][3][3];
int L[N] , R[N];
stack<int> st;
string s;

int dfs(int l , int r , int x , int y){
	if(R[l] == r && x != y) return -1;
	
	if(dp[l][r][x][y] >= 0) return dp[l][r][x][y];
	
	int mx = 0;
	if(R[l] == r){
		int v = cost[x];
		if(l + 1 == r) return v;
		
		for(int i = 0 ; i < 3 ; i ++){
			for(int j = 0 ; j < 3 ; j ++){
				if(x == i || y == j) continue;
				mx = max(mx , v + dfs(l + 1 , r - 1 , i , j));
			}
		}
	}else{
		for(int i = 0 ; i < 3 ; i ++){
			for(int j = 0 ; j < 3 ; j ++){
				if(i == j) continue;
				mx = max(mx , dfs(l , R[l] , x , i) + dfs(R[l] + 1 , r , j , y));
			}
		}
	}
	dp[l][r][x][y] = mx;
	return mx;
}

signed main(){
	freopen("bracket.in" , "r" , stdin);
	freopen("bracket.out" , "w" , stdout);
	
	cin >> n >> cost[1] >> cost[2] >> s;
	memset(dp , -1 , sizeof(dp));
	
	for(int i = 0 ; i < n ; i ++){
		if(s[i] == '(') st.push(i);
		else{
			int t = st.top();
			st.pop();
			R[t] = i;
			L[i] = t;
		}
	}
	int res = 0;
	for(int i = 0 ; i < 3 ; i ++){
		for(int j = 0 ; j < 3 ; j ++){
			res = max(res , dfs(0 , n - 1 , i , j));
		}
	}
	cout << res;
	return 0;
}

动态规划

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e3 + 5;

int n , cost[4] , dp[N][N][3][3];
int L[N] , R[N];
stack<int> st;
string s;


signed main(){
	freopen("bracket.in" , "r" , stdin);
	freopen("bracket.out" , "w" , stdout);
	
	cin >> n >> cost[1] >> cost[2] >> s;
	s = " " + s;
	
	for(int i = 1 ; i <= n ; i ++){
		if(s[i] == '(') st.push(i);
		else{
			int t = st.top();
			st.pop();
			R[t] = i;
			L[i] = t;
		}
	}
	int res = 0;
	
	for(int len = 2 ; len <= n ; len += 2){
		for(int l = 1 ; l <= n - len + 1 ; l ++){
			int r = l + len - 1;
			if(s[l] == ')' || s[r] == '(') continue;
			
			if(R[l] == r){
				if(len == 2){
					for(int i = 0 ; i < 3 ; i ++) dp[l][r][i][i] = cost[i];
				}else if(R[l + 1] == r - 1){
					for(int i = 0 ; i < 3 ; i ++) dp[l][r][i][i] = max(dp[l + 1][r - 1][(i + 1) % 3][(i + 1) % 3] , dp[l + 1][r - 1][(i + 2) % 3][(i + 2) % 3]) + cost[i];
					
				}else{
					for(int i = 0 ; i < 3 ; i ++) 
						for(int j = 0 ; j < 3 ; j ++)
							for(int k = 0 ; k < 3 ; k ++)
								if(i != k && j != k) dp[l][r][k][k] = max(dp[l][r][k][k] , dp[l + 1][r - 1][i][j]);
					
					for(int i = 0 ; i < 3 ; i ++) dp[l][r][i][i] += cost[i];
				}
			}else{
				if(R[l] == L[r] - 1){
					for(int i = 0 ; i < 3 ; i ++)
						for(int j = 0 ; j < 3 ; j ++)
							if(i != j) dp[l][r][i][j] = dp[l][R[l]][i][i] + dp[L[r]][r][j][j];
				}
				else{
					for(int i = 0 ; i < 3 ; i ++)
						for(int j = 0 ; j < 3 ; j ++)
							for(int k = 0 ; k < 3 ; k ++)
								if(i != k) dp[l][r][i][j] = max(dp[l][r][i][j] , dp[l][R[l]][i][i] + dp[R[l] + 1][r][k][j]);
				}
			}
		}
	}
	for(int i = 0 ; i < 3 ; i ++)
		for(int j = 0 ; j < 3 ; j ++)
			res = max(res , dp[1][n][i][j]);
			
	cout << res;
	return 0;
}

争取 $AK$