11133: 【原1133】数星星

题目

题目描述

author: Wen Xu 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/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

yyong119's solution

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string str;
int len;
long long ans_3, ans_2, ans_1;
long long s, t, a, r;
int main() {
    ios::sync_with_stdio(false);
    cin >> str;
    len = str.length();
    // calc ans_1
    for (int i = 0; i < len; ++i) {
        if (str[i] == 'S') ++s;
        if (str[i] == 'T') ++t;
        if (str[i] == 'A') ++a;
        if (str[i] == 'R') ++r;
    }
    ans_1 = s * t * a *r;
    // calc ans_2
    ans_2 = min(s, t);
    ans_2 = min(ans_2, a);
    ans_2 = min(ans_2, r);
    // calc ans_3
    s = t = a = r = 0;
    for (int i = 0; i < len; ++i) {
        if (str[i] == 'S') ++s;
        if (str[i] == 'T') ++t;
        if (str[i] == 'A') ++a;
        if (str[i] == 'R') ++r;
        t = min(s, t);
        a = min(t, a);
        r = min(a, r);
    }
    ans_3 = r;

    cout << ans_1 << " " << ans_2 << " " << ans_3;
    return 0;
}