解法
区间 dp 例题, 每次枚举分段点的时候先更新如果开始到结束区间端点有闭合的括号, 那么 dp[start][end]=dp[start+1][end-1]+2 其他照常枚举即可
代码
- #include <iostream>
- #include <cstring>
- using namespace std;
- int dp[666][666];
- int main()
- {
- iOS::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- string a;
- while(cin>>a)
- {
- if(a[0]=='e')
- break;
- memset(dp,0,sizeof(dp));
- for(int i=1;i<=a.size();i++)
- for(int j=0;j<a.size();j++)
- {
- int end=i+j-1;
- if(end>a.size()-1)
- continue;
- if((a[j]=='('&&a[end]==')')||(a[j]=='['&&a[end]==']'))
- dp[j][end]=dp[j+1][end-1]+2;
- for(int k=j;k<end;k++)
- dp[j][end]=max(dp[j][end],dp[j][k]+dp[k+1][end]);
- }
- cout<<dp[0][a.size()-1]<<"\n";
- }
- }
来源: http://www.bubuko.com/infodetail-2935013.html