区间dp
算是经典的区间dp问题
但是我上来写错了,,,唉
我的思路错了,还是要小心啊
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; int dp[110][110]; char s[110]; int n; bool check(char s1,char s2){ return (s1=='('&&s2==')')||(s1=='['&&s2==']'); } int main(){ while (scanf("%s",s+1)){ if (s[1]=='e')break; n = strlen(s+1); memset(dp,0,sizeof(dp)); for (int p=2;p<=n;++p){ for (int i=1,j=i+p-1;j<=n;++i,++j){ if (check(s[i],s[j]))dp[i][j]=dp[i+1][j-1]+2; for (int k=i;k<j;++k)dp[i][j]=max(dp[i][k]+dp[k+1][j],dp[i][j]); } } printf("%d\n",dp[1][n]); } }