进行了一次DP的练习,选几道题写一下博客~
『题目』
>> There!
给出 $n$ 个括号字符串(只包含’(‘,’)’),你需要从中选出一些字符串并对它们排序,使得它们连成一个字符串后构成一个匹配的字符串。求构成的字符串的最大长度~
『题解』
假如我们不考虑顺序,只考虑选择哪些字符串,我们很容易想到 dp[i][j] 表示在前 $i$ 个字符串中选出一些字符串使得 左括号的个数-右括号的个数 为 $j$。那么显然结果就是 dp[n][0]~其实还挺像01背包
但是我们不得不考虑如何安排原来字符串的顺序——因为我们dp转移时字符串的顺序是有影响的(不难理解,在转移时,我们要时刻保持‘(’数量≥’)’数量,但是假如第一个字符串是”)))”,第二个字符串是”(((“,直接按这种顺序我们就没法选择)
这样我们需要确定一开始的字符串的顺序……还挺像一道贪心题。
我们先把一个字符串转换为一个结构体:1
2
3
4
5struct 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$ 排序了。0$>
接下来就类似一个 01背包 的过程了——
至于“$j-del+Mindel\ge 0$” 就是说如果要选择第 $i$ 个字符串,那么它对 $j$ 的贡献应该是 $del$ ,所以 $j-del$ 就是上一次没有选择第 $i$ 个字符串时的 $j$ 。再加上 $Mindel$ 就是连接上第 $i$ 个字符串后从左到右计算 左括号-右括号 的最小值,如果它为负数,那么就存在一个位置到开头的 左括号 比 右括号 少,就不合法!
稍微一点细节就是注意判断 $j-del$ 过后会不会数组越界的问题了~
『源代码』
1 | /*Lucky_Glass*/ |
The End
Thanks for reading!
Email: lucky_glass@foxmail.com ,欢迎提问~