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

进行了一次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 ,欢迎提问~

0%