复杂度判断

原题题面

今天高川老师给大家讲解了算法复杂度（也可称为时间复杂度）的计算，并布置了作业题。高川在一个程序中写了很多个 for 循环，每一个 for 循环都是形如 for(int i = 1; i <= n; i++) ，且中间没有 continue，break 等影响循环执行的语句，即每一个 for 都会运行 n 轮（注意，并不是每一个循环里面定义的变量都叫 i，但是这个循环变量一定是从 1 到 n，执行 n 次）。现在高川想知道，他写的这个程序的算法复杂度是 n 的几次方。

在本题中，你可以将“算法复杂度”理解为“for循环最多嵌套的层数”。

输入描述

输入一个长度为 2n 的字符串，字符串的内容只可能是 0 或者 1，且 0 和 1 的数量相等。0 代表一个 for 循环的开始，1 代表一个 for 循环的结束。保证字符串合法。

输出描述

输出一行一个整数代表这个程序的算法复杂度是 n 的多少次方。

输出时每行末尾的多余空格，不影响答案正确性

样例输入1

001101

样例输出1

2

样例输入2

010101

样例输出2

1

样例解释2

样例 1 中，最多有两层循环嵌套，即 0011，所以算法复杂度是 n²，所以输出 2。

将样例 1 转化为代码即为：

for(int i = 1; i <= n; i++){
    for(int j = 1; j <= n; j++){

    }
}
for(int i = 1; i <= n; i++){

}

样例 2 中，最多有一层循环嵌套，所以输出 1。

解析

样例不够有说服力，让我们人造一组数据：

001100100111

如果我们将上面的数据转换成直观图：

如上图，把原本整齐的一串数字进行分层，你就会发现一下规律：

1. 复杂度取决于最后一行的复杂度（即最高复杂度）；
2. 遇0上一层，遇1下一层（想象成一个山陵，最左边也就是上行的都是0，反之为1）；

显而易见的，我们只需要设定一个变量来记录当前的层数即可。再记录下层数的最大值即可。

示例代码

#include
    <bits tdc++.h="">

using namespace std;
string s;
stack
     
       st;
long long maxn=-1;
int main(){
	cin>>s;
	long long law=0;
	for(int i=0;i
      <s.length();i++){ if(s[i]="='0'){" law++;="" st.push(law);="" }else{="" maxn="max(maxn,st.top());" st.pop();="" law--;="" }="" cout<<maxn;="" return="" 0;="" }<="" ode=""></s.length();i++){>
     
    </bits>

<p> </p> <p> </p> <p>这里有点复杂化，用了stack，不过直接用for循环就行了。笔者一开始看到这题就直接上了stack，不过现在看来并不是每一道带有“匹配”意味的题都要使用stack。</p> <p> </p>