首页 > 其他 > 详细

NYOJ 括号匹配系列2,5

时间:2014-05-03 23:52:04      阅读:625      评论:0      收藏:0      [点我收藏+]

本文出自:http://blog.csdn.net/svitter


括号匹配一:http://acm.nyist.net/JudgeOnline/problem.php?pid=2

括号匹配二:http://acm.nyist.net/JudgeOnline/problem.php?pid=15


之前被这个题目难住,现在看动态规划就顺便过来AC了它。结果发现当年被难住一点也不丢人。。

括号匹配一很简单,就是栈的应用,AC代码:

//============================================================================
// Name        : 括号匹配.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cstdio>
#include <string.h>
#include <stack>

using namespace std;

void ace(){
	int n;
	scanf("%d", &n);
	char ch;
	char tmp;
	ch = getchar();
	while(n --){
		stack <char> s;
		while((ch = getchar())!= ‘\n‘){
			if(s.empty())
				s.push(ch);
			else{
				tmp = s.top();
				if(tmp == ‘(‘ && ch == ‘)‘)
					s.pop();
				else if(tmp == ‘[‘ && ch == ‘]‘)
					s.pop();
				else
					s.push(ch);
			}
		}
		if(s.empty())
			printf("Yes\n");
		else
			printf("No\n");
	}
}


int main() {
	ace();
	return 0;
}
第二道就是DP题目了- -

真心被难住了。下面分析一下:

通过分析(别问我怎么分析的,画多了就看出来了- -)这必定是一个通过区间括号求和计算出的最小匹配括号值。

dp方程: dp [ i ] [ j ] = min ( dp [ i ] [ j ] , dp [ i ] [ k ] + dp [ k + 1 ] [ j ] );

dp[ i ][ j ] 表示当前匹配最小的括号值。后来发现这个不是正确的- -。因为这个阶段值与另一个阶段值会相互影响,违反了条件。


有重新做了分析:

发现无非就是这么几种情况:

" ..[ ... ] " + " ] “

" ..[ ... [ " + " ] "

" ..[ ... ] " + " [ "

" ..[ ... [ " + " [ "

这么四种情况。

如果假设dp [ i ] [ j ] = dp [ i ] [ j - 1 ] + 1

那么不符合情况的有第一种和第二种。而这两种情况就是因为中间串中有能够与最新加入的str[j]匹配的串。所以,当出现匹配串时,寻找最佳的匹配方案 —— dp [ i ] [ j ] = min ( dp [ i ] [ j ] , dp [ i ] [ k - 1 ] + dp [ k + 1 ] [ j - 1 ] );就是去除了两个括号,求括号里面的部分和括号外面部分的最小值。

特别的,为了针对 j  == i + 1的情况, dp [ i ] [ j ] = min ( dp [ i ] [ j ], dp [ i + 1] [ k - 1 ] + dp [ k + 1 ] [ j ])是不成立的。

AC代码:

//============================================================================
// Name        : 括号匹配.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cstdio>
#include <string.h>
#include <stack>

using namespace std;
#define min(a, b) a > b ? b : a

int dp[102][102];
char str[1001];

bool match(int i, int j)
{
    if (str[i] == ‘(‘ && str[j] == ‘)‘)
        return true;
    else if (str[i] == ‘[‘ && str[j] == ‘]‘)
        return true;
    else
        return false;
}

void ace()
{
    //case
    int c;
    scanf("%d", &c);
    getchar();

    //work point
    int i, j, k;

    //value
    int n;

    while (c--)
    {
        scanf("%s", str + 1); //此处可以尝试a+1
        memset(dp, 0, sizeof(dp));
        n = strlen(str + 1);

        //区间为差值为0时,必定需要一个括号匹配
        for (i = 1; i <= n; i++)
            dp[i][i] = 1;

        for (j = 2; j <= n; j++)        // j = 2...n
            for (i = j - 1; i >= 1; i--) // i = j...1
            {
                dp[i][j] = dp[i][j-1] + 1;
                for (k = i; k < j; k++)  //k = i+1...j-1
                {
                    if(match(k, j))
                    {
                        dp[i][j] = min(dp[i][j], dp[i][k-1] + dp[k + 1][j - 1]);
                    }
                }
            }

        printf("%d\n", dp[1][n]);
    }
}

int main()
{
    ace();
    return 0;
}



NYOJ 括号匹配系列2,5,布布扣,bubuko.com

NYOJ 括号匹配系列2,5

原文:http://blog.csdn.net/svitter/article/details/24877159

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!