题意: 给出一个的只有'(',')','[',']'四种括号组成的字符串, 求最长长度多少, end 结束
思路: 区间 dp,dp[i][j]表示区间 [i,j] 符合要求的长度
- #include<iostream>
- #include<algorithm>
- #include<cstring>
- #include<stack>
- #include<cmath>
- #include<queue>
- using namespace std;
- #define ll long long
- #define N 205
- #define rep(i,l,r) for(i=l;i<=r;i++)
- const int mod = 1e9 + 7;
- const int INF = 0x3f3f3f3f;
- #define eps 0.00000001// 偏差值 1e8
- #define pi acos(-1.0)// 高精度圆周率
- const int maxp = 1010; // 点的数量
- int a[N];
- int dp[N][N];
- int sum[N];
- int main()
- {
- int i, j, k;
- int n, ret = 0, m, maxn = 0, count = 0;
- int t, x, len;
- char s[N];
- while (cin>> s+1)
- {
- if (strcmp(s+1,"end")==0)
- break;
- n = strlen(s+1);
- memset(dp, 0, sizeof(dp));
- rep(len,2,n)
- {
- rep(i, 1, n)
- {
- j = i + len - 1;
- if (j> n)break;
- if (s[i] == '(' && s[j] == ')' || s[i] == '[' && s[j] == ']')
- dp[i][j] = dp[i + 1][j - 1] + 2;
- rep(k, i, j - 1)
- {
- dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j]);
- }
- }
- }
- cout << dp[1][n] << endl;
- }
- }
来源: http://www.bubuko.com/infodetail-3502159.html