P10472 括号画家
use_long_long · · 题解
思路
这题要用栈来做。
这道题我们可以先考虑从简单的入手：如何判断一个括号序列是否合法。
这个可以如果是左括号加入栈内。 如果是右括号的话就看一下栈顶元素是否和它匹配。 如果不匹配就不是一个合法的括号序列。
然后到这道题上就稍微转化一下。
你需要对于每个右括号找到与之相匹配的左括号。
然后对这个取个
代码时间~~~
好，我们写完了这个就可以自己尝试写一下这道题的代码了。
40 分 code
#include<algorithm> //含sort函数等
#include<cmath> //关于数学函数的头文件
#include<cstring> //string字符串头文件
#include<cstdio> //C语言的头文件
#include<iomanip> //用于cout<<fixed<<setprecision()
#include<iostream> //含cin,cout
#include<queue> //普通队列(只能一边进一边出)(先进先出)
#include<deque> //双向队列(两边都可以进出)(先进先出)
#include<stack> //栈(先进后出，后进先出)
#include<list> //列表
#include<vector> //动态数组
#include<map> //关联式容器
#include<set> //集合
#include<climits> //INT_MAX与INT_MIN
using namespace std;
string s;
stack<int>stk;
int len;
int sum,ans=0;
int main()
{
cin>>s;
len=s.size();
for(int i=0;i<len;i++){
if(s[i]=='('||s[i]=='['||s[i]=='{'){
stk.push(i);
continue;
}
if(!stk.empty()){
if(((s[i]==')'&&s[stk.top()]=='(')||(s[i]==']'&&s[stk.top()]=='[')||(s[i]=='}'&&s[stk.top()]=='{'))){
ans=max(ans,i-stk.top()+1);
stk.pop();
}else{
while(!stk.empty()){
stk.pop();
}
}
}
}
cout<<ans<<endl;
return 0; //每日一个好习惯，老师远离我
}结果。
为什么是四十分呢？
显然，我们的代码在遇到 ()()() 的时候会出问题，正确答案显然是
怎么改呢？
我们可以记录一下当前这个序列的开始点，也就是括号序列的最左合法的括号点是多少。
72 分 code
#include<algorithm> //含sort函数等
#include<cmath> //关于数学函数的头文件
#include<cstring> //string字符串头文件
#include<cstdio> //C语言的头文件
#include<iomanip> //用于cout<<fixed<<setprecision()
#include<iostream> //含cin,cout
#include<queue> //普通队列(只能一边进一边出)(先进先出)
#include<deque> //双向队列(两边都可以进出)(先进先出)
#include<stack> //栈(先进后出，后进先出)
#include<list> //列表
#include<vector> //动态数组
#include<map> //关联式容器
#include<set> //集合
#include<climits> //INT_MAX与INT_MIN
using namespace std;
string s;
stack<int>stk;
int len;
int sum,ans,l=-1;
int main()
{
cin>>s;
len=s.size();
for(int i=0;i<len;i++){
if(s[i]=='('||s[i]=='['||s[i]=='{'){
if(l==-1){
l=i;
}
stk.push(i);
continue;
}
if(!stk.empty()){
if(((s[i]==')'&&s[stk.top()]=='(')||(s[i]==']'&&s[stk.top()]=='[')||(s[i]=='}'&&s[stk.top()]=='{'))){
ans=max(ans,i-stk.top()+1);
if(stk.size()==1){
ans=max(ans,i-l+1);
}
stk.pop();
}else{
while(!stk.empty()){
stk.pop();
}
l=-1;
}
}else{
l=-1;
}
}
cout<<ans<<endl;
return 0; //每日一个好习惯，老师远离我
}结果。
Why?
我们很容易看出，但我们的代码遇到 [()()} 时有问题。
怎么办？
如果说当前已经可以匹配了，并且不剩左括号了，就记录一下当前左括号位置就行了。
AC code
#include<algorithm> //含sort函数等
#include<cmath> //关于数学函数的头文件
#include<cstring> //string字符串头文件
#include<cstdio> //C语言的头文件
#include<iomanip> //用于cout<<fixed<<setprecision()
#include<iostream> //含cin,cout
#include<queue> //普通队列(只能一边进一边出)(先进先出)
#include<deque> //双向队列(两边都可以进出)(先进先出)
#include<stack> //栈(先进后出，后进先出)
#include<list> //列表
#include<vector> //动态数组
#include<map> //关联式容器
#include<set> //集合
#include<climits> //INT_MAX与INT_MIN
using namespace std;
const int MAX=10000+5;
string s;
stack<int>stk;
int len;
int f[MAX];
int sum,ans,l=-1;
int main()
{
cin>>s;
len=s.size();
memset(f,127/3,sizeof(f));
for(int i=0;i<len;i++){
if(s[i]=='('||s[i]=='['||s[i]=='{'){
if(l==-1){
l=i;
}
stk.push(i);
continue;
}
if(!stk.empty()){
if(((s[i]==')'&&s[stk.top()]=='(')||(s[i]==']'&&s[stk.top()]=='[')||(s[i]=='}'&&s[stk.top()]=='{'))){
f[i]=min(stk.top(),f[stk.top()-1]);
ans=max(ans,i-f[i]+1);
stk.pop();
}else{
while(!stk.empty()){
stk.pop();
}
l=-1;
}
}else{
l=-1;
}
}
cout<<ans<<endl;
return 0; //每日一个好习惯，老师远离我
}就是这样维护一个