poj-2955 Brackets

2016年07月18日 |

acm

| acm

• 题目：
• 代码：
• 解析&吐槽：

题目：

Brackets
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 5959 Accepted: 3178

Description

We give the following inductive definition of a “regular brackets” sequence:

    the empty sequence is a regular brackets sequence,
    if s is a regular brackets sequence, then (s) and [s] are regular brackets sequences, and
    if a and b are regular brackets sequences, then ab is a regular brackets sequence.
    no other sequence is a regular brackets sequence

For instance, all of the following character sequences are regular brackets sequences:

    (), [], (()), ()[], ()[()]

while the following character sequences are not:

    (, ], )(, ([)], ([(]

Given a brackets sequence of characters a1a2 … an, your goal is to find the length of the longest regular brackets sequence that is a subsequence of s. That is, you wish to find the largest m such that for indices i1, i2, …, im where 1 ≤ i1 < i2 < … < im ≤ n, ai1ai2 … aim is a regular brackets sequence.

Given the initial sequence ([([]])], the longest regular brackets subsequence is [([])].

Input

The input test file will contain multiple test cases. Each input test case consists of a single line containing only the characters (, ), [, and ]; each input test will have length between 1 and 100, inclusive. The end-of-file is marked by a line containing the word “end” and should not be processed.

Output

For each input case, the program should print the length of the longest possible regular brackets subsequence on a single line.

Sample Input

((()))
()()()
([]])
)[)(
([][][)
end

Sample Output

6
6
4
0
6

代码：

// oj.cpp : 定义控制台应用程序的入口点。
//

#include <iostream>
#include <limits>
#include <algorithm>
#include <numeric>
#include <string>
#include <utility>
#include <cstdlib>
//#include <cstdio>

using namespace std;

string L;

long long dp[110][110];

long long getres(int i, int j)
{
    if (i >= j)
        return 0;

    if (dp[i][j] != -1)
        return dp[i][j];

    bool pipei = false;
    if (L[i] == '('&&L[j] == ')')
        pipei = true;
    else if (L[i] == '['&&L[j] == ']')
        pipei = true;

    dp[i][j]=0;

    if (pipei)
        dp[i][j] = getres(i + 1, j - 1) + 2;

    for (int k = i;k < j;++k)
        dp[i][j] = max(getres(i, k) + getres(k + 1, j), dp[i][j]);

    return dp[i][j];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    while (cin >> L&&L != "end")
    {
        memset(dp, -1, sizeof(dp));

        cout << getres(0, L.size() - 1) << endl;
    }
}

解析&吐槽：

网上的题解大多都是递推解的，我这里贴上一个记忆化搜索的版本。

经典的动态规划题目，设 dp[i][j] 为 i、j 之间最多的配对括号数，递推分两种情况：

1. L[i]==L[j] :: 有可能因为 i、j 配对而多出来两个括号，因此是 dp[i+1][j-1]+2 。
2. L[i]!=L[j] :: 枚举所有的字母，将当前区间断成两个子区间，找到两个子区间相加最大的情况。

坑点有二：

1. 即使 L[i]==L[j] ，也有可能是把当前区间断开取子区间可以得到最优解。因此即使相等，也 必须枚举断开区间的情况。
2. 一定要注意第二种情况里面递推的区间，我这里面的 k 要从 i 枚举到 j-1。因为如果 k 取 i， 子区间就是单独的 i 和排除 i 剩下的区间；取 j-1 时是单独的 j 和排除 j 的子区间。 我一开始做的时候就是因为把枚举区间写成了从 i+1 到 j-1 而狂 wa。

关于题目也是有一些槽点，尽管题目一开始说只有配对的括号里的所有括号也是配对的时候这对括号 才是配对的，但是最后又说可以“任选”子序列使得子序列的所有括号都是配对的，也就是说子序列 不一定非得连续。总而言之只需要找到配对的括号，计算它们的数量即可，不需要管括号里面的括号 是否配对。我感觉如果题目要求是里面的括号也要配对的话可以把函数的开头两句改成这样：

if (i == j)
  return -2;
else if (i > j)
  return 0;

不过我也不知道这样到底对不对，毕竟没试过_(:зゝ∠)_