C++-POJ2955-Brackets[DP]
题意就是，找出最长合法子括号序列
容易想到设f[l][r]为l~r的最长合法子括号序列的长度
然后从短的状态往长的状态枚举，不断更新答案就可以了
1 //#include<bits/stdc++.h> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 char s[101];int f[101][101]; 7 int DP(int n){ 8 memset(f,0,sizeof(f)); 9 for(int len=2;len<=n;len++) 10 for(int l=1;l+len-1<=n;l++){int r=l+len-1; 11 if((s[l]=='('&&s[r]==')')||(s[l]=='['&&s[r]==']'))f[l][r]=max(f[l][r],f[l+1][r-1]+2); 12 for(int i=l;i<r;i++)f[l][r]=max(f[l][r],f[l][i]+f[i+1][r]); 13 } 14 return f[1][n]; 15 } 16 int main(){ 17 while(scanf("%s",s+1)&&s[1]!='e')printf("%d ",DP(strlen(s+1))); 18 return 0; 19 }