题目链接：https://arena.topcoder.com/index.html#/u/practiceCode/17960/104480/15780/2/334016
题目大意：(和）的任意组合串，如果（）配对则串就是balance的，一个串中所有balance的子串的个数为beauty值。任给串求最大的可能beauty值。
算法：首先想到可以dp求一个串的beauty值，然后枚举串的可能求最大值即可，但很显然，很麻烦而且枚举串要n!，估计超时。那怎么办呢？分析最大值串的特点，都是()()..()形式，答案也就明显了=min(o, c)*min(
实现：topcoder要写类，方法要定义成public。
代码：
#include<string>
#include<algorithm>
using namespace std;
class MaximumBalances {
public:
int solve(string s) {
int o=0, c =0, ans;
for(int i=0; i<s.length(); i++) {
if(s[i] == '(') ++o;
else ++c;
}
ans = min(o, c) * (min(o, c)+1)/2 ;
return ans;
};
};
网友评论