在听这个，很上头。

今天挺逆天，就树的那道题有 $60$ 分qwq，写不下去了。

T1 Porcelain

题面

原题面 CF148E

$n$ 个货架，用二维数组表示价值，每个货架只能取出头部若干和尾部若干。取 $m$ 个物品价值之和最大多少。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int dp[N][M];
int val[N][N];
int num[N][N];
int siz[N];
int pre[N],suf[N];
int n,m;
signed main(){
	//输入
	n=read(); m=read();
	for(int i=1;i<=n;i++){
		siz[i]=read();
		for(int j=1;j<=siz[i];j++){
			num[i][j]=read();
		}
	}
	//预处理 val[i][j] 第 i 个货架选 j 个最大贡献
	for(int i=1;i<=n;i++){
		memset(pre,0,sizeof pre);
		memset(suf,0,sizeof suf);
		for(int j=1;j<=siz[i];j++) pre[j]=pre[j-1]+num[i][j];
		for(int j=siz[i];j>=1;j--) suf[j]=suf[j+1]+num[i][j];
		for(int j=1;j<=siz[i];j++){
			for(int k=0;k<=j;k++){
				int ls=k,rs=j-k;//左边取 k 个，右边 j-k 个
				val[i][j]=max(val[i][j],pre[ls]+suf[siz[i]+1-rs]);
			}
		}
	}
	//dp[i][j] 前 i 个货架取 j 个物品的最大贡献
	//memset(dp,~0x3f,sizeof dp);
	dp[0][0]=0;
	for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) for(int k=0;k<=min(siz[i],j);k++){
		dp[i][j]=max(dp[i][j],dp[i-1][j-k]+val[i][k]);
		//cout<<dp[i][j]<<" "<<dp[i-1][j-k]<<"+"<<val[i][k]<<endl;
	}
	cout<<dp[n][m]<<endl;
	return 0;
}

T2 邪恶之书

题面

原题面 Luogu

给一棵树，树上有若干关键节点，计算有多少节点到所有关键节点的距离都不超过 $d$ 。

思路

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
int n,m,d;
int s[N],t[N],f[N],h[N],g[N],dis[N],val[N];
vector <int> G[N];
void dfs1(int u,int fa){
	f[u]=h[u]=g[u]=-inf;
	if(val[u]) f[u]=0;
	for(auto v:G[u]){
		if(v==fa) continue;
		dfs1(v,u);
		f[u]=max(f[u],f[v]+1);
	}
}
void dfs2(int u,int fa){
	if(fa){
		for(auto v:G[u]){
			if(v==fa) continue;
			h[v]=max(h[v],h[u]+1);
		}
	}
	int tmp=-inf;
	for(auto v:G[u]){
		if(v==fa) continue;
		h[v]=max(h[v],tmp);
		tmp=max(tmp,f[v]+1);
	}
	tmp=-inf;
	reverse(G[u].begin(),G[u].end());
	for(auto v:G[u]){
		if(v==fa) continue;
		h[v]=max(h[v],tmp);
		tmp=max(tmp,f[v]+1);
	}
	for(auto v:G[u]){
		if(v==fa) continue;
		if(val[u]) h[v]=max(h[v],0);
		g[v]=max(f[v],h[v]+1);
		dfs2(v,u);
	}
}
signed main(){
	n=read(),m=read(),d=read();
	for(int i=1;i<=m;i++) val[read()]=1;
	for(int i=1;i<n;i++){
		int u=read(),v=read();
		G[u].push_back(v);G[v].push_back(u);
	}
	dfs1(1,0);
	g[1]=f[1];
	dfs2(1,0);
	int ans=0;
	for(int i=1;i<=n;i++){
		if(g[i]<=d) ans++;
	}
	cout<<ans<<endl;
	return 0;
}

T3

还没写完，题面 Luogu 。

T4 Coloring Brackets

题面

原题面 CF149D

给括号序列每个半括号，要求：

    1. 不染色或者染红/蓝色；
    1. 一对括号正好有一半染色；
    1. 相邻括号不能染相同颜色。

求方案数。

思路

$dp[l][r][a][b]$ 表示区间 $[l,r]$ 两端点的染色状态分别为 $a$ 和 $b$ （$a,b \in \left\{ 0,1,2 \right\} $）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
stack <pc> st;
int re[N];//相匹配括号的位置
int dp[N][N][3][3];//0,1,2三种颜色
int ans=0;
int c[N];
void dfs(int l,int r){
	if(r==l+1) dp[l][r][0][1]=dp[l][r][0][2]=dp[l][r][1][0]=dp[l][r][2][0]=1;
	else if(re[l]==r){
		dfs(l+1,r-1);
		for(int i=0;i<=2;i++){
			for(int j=0;j<=2;j++){
				if(j!=1)dp[l][r][0][1]+=dp[l+1][r-1][i][j],dp[l][r][0][1]%=P;
				if(j!=2)dp[l][r][0][2]+=dp[l+1][r-1][i][j],dp[l][r][0][2]%=P;
				if(i!=1)dp[l][r][1][0]+=dp[l+1][r-1][i][j],dp[l][r][1][0]%=P;
				if(i!=2)dp[l][r][2][0]+=dp[l+1][r-1][i][j],dp[l][r][2][0]%=P;
			}
		}
	}else{
		dfs(l,re[l]);
		dfs(re[l]+1,r);
		for(int i=0;i<=2;i++) for(int j=0;j<=2;j++) for(int p=0;p<=2;p++) for(int q=0;q<=2;q++){
			if(j==1&&p==1||j==2&&p==2) continue;
			dp[l][r][i][q]+=(dp[l][re[l]][i][j]*dp[re[l]+1][r][p][q]%P);
			dp[l][r][i][q]%=P;
		}
	}
	
}
signed main(){
	ios::sync_with_stdio(false);
	string s; cin>>s;
	int n=s.length(); s="?"+s;
	for(int i=1;i<=n;i++){
		if(st.empty()) st.push({s[i],i});
		pc k=st.top();
		if(k.first=='('&&s[i]==')'){
			st.pop();
			re[i]=k.second;
			re[k.second]=i;
		}else{
			
			st.push({s[i],i});
		}
	}
	dfs(1,n);
	int ans=0;
	for(int i=0;i<=2;i++) for(int j=0;j<=2;j++){
		ans+=dp[1][n][i][j],ans%=P;
	}
	cout<<ans<<endl;
	return 0;
}