首页 > ACM题库 > HDU-杭电 > HDU 3351-Seinfeld-动态规划-[解题报告]HOJ
2014
03-16

HDU 3351-Seinfeld-动态规划-[解题报告]HOJ

Seinfeld

问题描述 :

I’m out of stories. For years I’ve been writing stories, some rather silly, just to make simple problems look difficult and complex problems look easy. But, alas, not for this one.
You’re given a non empty string made in its entirety from opening and closing braces. Your task is to find the minimum number of “operations” needed to make the string stable. The definition for being stable is as follows:
1. An empty string is stable.
2. If S is stable, then {S} is also stable.
3. If S and T are both stable, then ST (the concatenation of the two) is also stable.
All of these strings are stable: {}, {}{}, and {{}{}}; But none of these: }{, {{}{, nor {}{.
The only operation allowed on the string is to replace an opening brace with a closing brace, or visa-versa.

输入:

Your program will be tested on one or more data sets. Each data set is described on a single line. The line is a non-empty string of opening and closing braces and nothing else. No string has more than 2000 braces. All sequences are of even length.
The last line of the input is made of one or more ’-’ (minus signs.)

输出:

Your program will be tested on one or more data sets. Each data set is described on a single line. The line is a non-empty string of opening and closing braces and nothing else. No string has more than 2000 braces. All sequences are of even length.
The last line of the input is made of one or more ’-’ (minus signs.)

样例输入:

}{
{}{}{}
{{{}
---

样例输出:

1. 2
2. 0
3. 1

题意:给出一个由’{‘ , ‘}’ 组成的字符串,通过改变最少括号的方向使其匹配。

思路:一开始用区间dp,TLE了,贪心才能过。贪心方法:从左向右遍历,遇到左括号lef++,遇到右括号,若lef>0,lef–,否则右括号变为左括号,ans++,lef++,最后再加上多下来的左括号,即lef/2。

 

先给出TLE代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=2005;
char str[maxn];
int dp[maxn][maxn], len;
int match(int x, int y){
    return (str[x]=='}') + (str[y]=='{');
}

int solve(int x, int y){
    if(x>y)return 0;
    if(dp[x][y]!=-1)return dp[x][y];
    int i, tmp=maxn;
    for(i=x+1; i<y-1; i+=2){
        if(solve(x, i)+solve(i+1, y)<tmp){
            tmp=solve(x, i)+solve(i+1, y);
        }
    }
    if(match(x, y)+solve(x+1, y-1)<tmp){
        tmp=match(x, y)+solve(x+1, y-1);
    }
    dp[x][y]=tmp;
    return tmp;
}

int main(){
    int cas=1;
    while(scanf("%s", str)&&str[0]!='-'){
        memset(dp, -1, sizeof(dp));
        len=strlen(str);
        printf("%d. %d\n", cas++, solve(0, len-1));
    }
    return 0;
}

 

下面是贪心的AC代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=2005;
char str[maxn];

int main(){
    int cas=1;
    while(scanf("%s", str)&&str[0]!='-'){
        int i, ans=0, lef=0;
        for(i=0; str[i]!='\0'; i++){
            if(str[i]=='{'){
                lef++;
            }
            else if(lef>0){
                lef--;
            }
            else {
                ans++;lef++;
            }
        }
        printf("%d. %d\n", cas++, ans+lef/2);
    }
    return 0;
}

 

参考:http://blog.csdn.net/taozifish/article/details/8094996


  1. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  3. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。