链接：https://ac.nowcoder.com/acm/contest/332/I
来源：牛客网
一行一个01串 s ，|s| 表示天数，si=0si=0 表示 wzoi 第 i 天推荐 noip 题， si=1si=1 表示 wzoi 第 i 天推荐省选题。
一行一个整数最大得分。
全部的输入数据满足：1≤n≤1061≤n≤106 , n 为偶数。
出题人的题解：
令看题为左括号，做题为右括号，就可以用一个括号序列表示行动序列。
那么一个括号序列的价值就是，对于每个匹配的括号，如果他们推荐种类相同，+10分，否则+5分。
如果 s 中有两个连续的1或0，那么可以让他们匹配，然后删去他们，递归处理。
最终剩下来的一定是1,0交错，这时一定无法让两个相同种类匹配了，贡献可以直接算。
时间复杂度 O(n)
出题人的代码：
#include<bits/stdc++.h> using namespace std; #define rep(i,l,r) for(int i=l;i<=r;++i) int main() { //freopen("data10.in","r",stdin);freopen("data10.out","w",stdout); string a,b; cin>>a; //cerr<<a.size()<<" "<<b.size()<<endl; for(auto c:a) if(b.empty()||b.back()!=c)b.push_back(c); else b.pop_back(); printf("%d\n",5*(a.size()-b.size()/2)); }
我ac的代码：
#include<bits/stdc++.h> using namespace std; int main() { stack<char>s; string s1; cin>>s1; int sum=0; for(int i=0; i<s1.length(); i++) { if(s.empty()) { s.push(s1[i]); continue; } if(s.top()==s1[i]) { sum+=10; s.pop(); } else s.push(s1[i]); } cout<<sum+s.size()/2*5<<endl; }
原文：https://www.cnblogs.com/tp25959/p/10350209.html