poj 2955 Brackets（区间dp....括号匹配。。。人生第一道区间dp）
题意：给出若干括号，问最大匹配数是多少。
思路：没有思路。我知道这是dp。。。然后其他就什么都不知道了。。。转移方程？ 完全没思路。。知道了转移方程。。。。嗯，还是不会。。。边界怎么写？状态怎么推？循环顺序? 循环次序？我一点思路都没有。。。。。
人生中第一道区间dp(这话我都说了不知道多少次了。。。每次都学不会。。。。sad)
我的dp水平和其他部分的水平还真是不匹配。。。
看了题解。。。自己写（抄）了一遍。。还是觉得好玄学。。。
细节见代码。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年07月25日 星期一 15时12分28秒
4File Name :code/poj/2955.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=105;
34char st[N];
35int dp[N][N];
36
37bool check(char a,char b)
38{
39 //cout<<"a:"<<a<<" b:"<<b<<endl;
40 if((a=='['&&b==']')||(a=='('&&b==')')) return true;
41 return false;
42
43}
44int main()
45{
46 #ifndef ONLINE_JUDGE
47 freopen("code/in.txt","r",stdin);
48 #endif
49
50 while (~scanf("%s",st))
51 {
52 if (st[0]=='e') break;
53 ms(dp,0);
54 int len = strlen(st);
55
56 for ( int l = 1 ; l < len ; l++) //枚举区间长度,区间dp好像经常要这样？
57 //区间长度要从小到大枚举，原因是计算较长区间的答案的时候，需要用到较短区间的值。
58 //所以要先算所有区间为1的，再算所有区间为2的...
59 for ( int i = 0 ,j = l ; j < len ; i++,j++)
60 {
61 if(check(st[i],st[j]))
62 dp[i][j] = dp[i+1][j-1]+2; //如果当前匹配，那么匹配数在原有的基础（区间i+1到j-1）上+2
63
64 for ( int k = i ; k < j ; k++) //由于区间具有累加性，意思是区间[i,j]的匹配数等于区间[i,k]和区间[k+1,j]的匹配数的和。
65 dp[i][j] = max(dp[i][j],dp[i][k]+dp[k+1][j]); //但是我们不知道在哪里划分区间最大，所以枚举划分的点，取最大。
66 // cout<<"dp[i][j]:"<<dp[i][j]<<endl;
67 }
68
69 printf("%d\n",dp[0][len-1]);
70
71
72 }
73
74 #ifndef ONLINE_JUDGE
75 fclose(stdin);
76 #endif
77 return 0;
78}