SJTU OJ 1133. 数星星
Description
主任和小伙伴晚上非常无聊，于是带着他的宠物狗出来走走。主任突然发现天空中有一条长度为N的字符串，里面的字符都是大写字母。于是主任和他的小伙伴们开始数星星(STAR)。
主任和他的小伙伴还有宠物狗数星星的数法不太一样。小伙伴是一个很教条的人，他只喜欢有规则的东西。所以他每次会在字符串里面找最早的’S’，然后找’S’之后最早的’T’，然后找’T’之后最早的’A’，最后找’A’之后最早的’R’。也就是找一个位置最靠前的STAR的子序列。每次找到这样一个子序列，小Z就数到一个星星，然后把这个子序列删掉，并继续，直到找不到星星为止。
宠物狗喜欢简单一些的东西。它每次只是随便找S,T,A,R各一个，算一个星星，并把字母删掉。
主任不喜欢删掉星星，所以他每次随便选S，T，A，R各一个，算一个星星。但是主任记忆力很好，相同位置组合的星星主任是不会重复数的。
现在要你来算算主任、他的宠物狗、还有小伙伴分别最多可以数到几个星星。
Input Format
共1行。
第一行：一个字符串S,没有多余字符，最后有换行符。
Output Format
三个整数，用空格隔开，分别是主任、宠物狗和小伙伴数到的星星数。
Sample Input 1
STAR
Sample Output 1
1 1 1
Limits
30% N<=10 60% N<=60 100% N<=1000
题目经过分析之后 其实就是求三个值 （s表示S出现的次数....）
int star[4][N];//0S 1T 2A 3R 第二维的长度表示有该字符的个数,记录的是这些字符的位置int cur[4]={ 0};//记录fri使用的光标 //四个字符当前走到的光标 如果满足 star[i][cur[i]] 此方法看似没错...但是只能20分...暂时还没找到错误之处...留作以后慢慢分析...
第二种方法: 扫描维护法 也是一种在线计算的方法(在线计算的意思是:随时停止输入都能得到之前输入的结果)
这个思路的核心是这样的,若某一次输入之后s<t了，那么至少有一个t是用不到的,这个用不到指的是 根本连ST都组成不了 因为此时的s指的是前面所有输入中s的个数,
那么如果s>t表示当前输入的T一定可以组成ST子串，所以t的个数指的是一定可以组成ST的数量依次类推
如果我们保持s>=t>=a 那么a的个数指的是 一定可以组成STA子串的数量
如果保持s>=t>=a>=r 那么最后的r表示的是一定可以组成STAR的数量 也就是答案
int s(0),t(0),a(0),r(0); for (int i = 0; i < n; ++i) { switch(sky[i]){ case 'S': s++;break; case 'T': //注意 接下来的所有维护条件里的s t a 都是在此次输入之前的结果 所以如果s>t表示新输入的T一定会用得上//此处的用得上是相对于之前的S来说的,最终能不能成为完整的子序列还不知道 if(s>=(t+1))//如果此T是用得上的 那么就记入 注意是一定用得上 t++; break;//如果此T根本不会组成ST 就不记入 case 'A': if(t>=a+1) a++;//因为可以组成STA break; case 'R': if(a>=r+1) r++;//可以组成STAR break; } } fri = r;//最后的r就是答案