OI题解 - Karp-de-Chant Number(BZOJ-4922) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI题解 - Karp-de-Chant Number(BZOJ-4922)

发表于 更新于 分类于 Valine：

进行了一次DP的练习，选几道题写一下博客~

『题目』

>> There!
给出 $n$ 个括号字符串（只包含’(‘,’)’），你需要从中选出一些字符串并对它们排序，使得它们连成一个字符串后构成一个匹配的字符串。求构成的字符串的最大长度~

『题解』

假如我们不考虑顺序，只考虑选择哪些字符串，我们很容易想到 dp[i][j] 表示在前 $i$ 个字符串中选出一些字符串使得 左括号的个数-右括号的个数 为 $j$。那么显然结果就是 dp[n][0]~其实还挺像01背包

但是我们不得不考虑如何安排原来字符串的顺序——因为我们dp转移时字符串的顺序是有影响的（不难理解，在转移时，我们要时刻保持‘(’数量≥’)’数量，但是假如第一个字符串是”)))”，第二个字符串是”(((“，直接按这种顺序我们就没法选择）
这样我们需要确定一开始的字符串的顺序……还挺像一道贪心题。
我们先把一个字符串转换为一个结构体：

1
2
3
4
5
struct NODE{
	int del, //左括号-右括号
		Mindel, //对于字符串的每一个位置i，求出开头到i的左括号数量-右括号数量，Mindel是它们的最小值
		len; //字符串长度
};

为什么要储存这些值？显然是有用的……
第一个贪心性质比较简单——按 $del$ 从大到小排序，然后将 $del\ge 0$ 和 $del<0$ 分成前后两半。 第二个贪心是**把前一半按 $mindel$ 从大到小排序**。因为 越大，就说明剩下来的左括号数量越多，那么就越能和接下来的右括号匹配（毕竟在转移时，我们允许暂时存在左括号数量>右括号数量，但是绝对不能右括号数量>左括号数量！）
第三个贪心是把后一半按 $del-Mindel$ 从大到小排序。$del-Mindel$ 是什么呢？如果我们把 $del$ 也看成一个前缀和（也就是从开头到末尾的前缀和），那么 $del-Mindel$ 就可以看成一个 后缀和 .显然对于字符串的第 $i$ 个位置，$1$~$i$ 的前缀和 加上 $i+1$~$len$ 的后缀和 就是 $del$ ，因为此时的前缀和最小，那么后缀和就最大。因为del<0，所以Mindel<0，也就是右括号比左括号多，则“后缀和大”说明 (右括号数量-左括号数量) 越小，其实就是多余的右括号越少。那么显然我们更容易让少量右括号与多余的左括号匹配，所以就按 $del-Mindel$ 排序了。

接下来就类似一个 01背包 的过程了——

至于“$j-del+Mindel\ge 0$” 就是说如果要选择第 $i$ 个字符串，那么它对 $j$ 的贡献应该是 $del$ ，所以 $j-del$ 就是上一次没有选择第 $i$ 个字符串时的 $j$ 。再加上 $Mindel$ 就是连接上第 $i$ 个字符串后从左到右计算 左括号-右括号 的最小值，如果它为负数，那么就存在一个位置到开头的 左括号 比 右括号 少，就不合法！
稍微一点细节就是注意判断 $j-del$ 过后会不会数组越界的问题了~

『源代码』

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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=300;
struct NODE{
	int del,Mindel,len;
//	NODE(){Mindel=(1<<30);}
}nod[N+7];
bool cmp1(NODE A,NODE B){return A.del>B.del;}
bool cmp2(NODE A,NODE B){return A.Mindel>B.Mindel;}
bool cmp3(NODE A,NODE B){return A.del-A.Mindel>B.del-B.Mindel;}
int n,Maxdel;
int dp[N+7][N*N+7];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		char str[N+7]="";
		scanf("%s",str);
		nod[i].len=strlen(str);
		for(int j=0;j<nod[i].len;j++)
			nod[i].del+=(str[j]=='('? 1:-1),
			nod[i].Mindel=min(nod[i].Mindel,nod[i].del),
			Maxdel+=(str[j]=='('? 1:0);
	}
	sort(nod+1,nod+n+1,cmp1);
	int pos=n+1;
	for(int i=1;i<=n;i++)
		if(nod[i].del<0){
			pos=i;
			break;
		}
	sort(nod+1,nod+pos,cmp2);
	sort(nod+pos,nod+n+1,cmp3);
	memset(dp,200,sizeof dp);
	dp[0][0]=0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=Maxdel;j++){
			dp[i][j]=dp[i-1][j];
			if(j-nod[i].del>=0 && j-nod[i].del<=Maxdel && j-nod[i].del+nod[i].Mindel>=0)
				dp[i][j]=max(dp[i][j],dp[i-1][j-nod[i].del]+nod[i].len);
		}
	}
	printf("%d\n",dp[n][0]);
	return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com ，欢迎提问~