题解 P3056 【[USACO12NOV]笨牛Clumsy Cows】
A_Big_Jiong · · 题解
我实在想不明白，为什么这个题会和前缀和有关系，肯定是本蒟蒻太弱了，根本想不出来。
我的思路其实也十分简单，但由于太弱，优化是不可能优化的
（绝对不会真香警告），主要就是通过模拟栈顶，来记录有多少的括号是需修改的，具体我还是在代码中说吧。
#include<cstdio>
#include<cstring>//便于使用strlen();
using namespace std;
const int maxn=100010;
char str[maxn];//我也不知道用const开数组的习惯从何而来，先这样吧
int ans,ls,num;//ans即answer,ls即str字符串的长度,num就是个假栈顶,说明现在已经有num个括号未匹配成功
int main(){
scanf("%s",&str);
ls=strlen(str);//记录str的长度，不要问我为什么不用STL
for(int i=0;i<ls;i++){
if(str[i]=='(') num++;//等待匹配右括号
else if(str[i]==')'&&num==0){//num==0即为现在str[i]之前所有括号都能匹配，凭空出现个右括号,ans自加,并将该括号转为左括号等待匹配
ans++;num++;
}else num--;//匹配成功后要减少一个待匹配的数量
}
ans+=num/2;//还有num个左括号没有匹配,便将其中的一半转为右括号
if(num%2!=0) ans++;//如果num是单数,则有一个括号必须进行一次删除修改
//值得一提的是，楼上的dalao用的ans+=(num+1)/2;和此思路一致，也更加巧妙，我太弱所以没想到
printf("%d",ans);
return 0;
}这次话比较多，代码被挤得很不美观(虽然我这人毫无美学观念)，还请各位大佬多多包涵，同时，也欢迎提出新解法让我观摩。