2014
03-16

# 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

#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;
}

#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;
}

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