描述
计算鸭在玩开心消消乐的时候，想到了一种新的消消乐，如下：

给定一个字符串 aa ，仅包含A、B两种字符，现在需要你将字符串aa进行消除，使得最终得分最大，消除规则为：

AB为5分，BB为3分，A为1分，B为1分。

求最大消除分数。

输入
第一行为字符串aa，保证1 leq len(a) leq 30001≤len(a)≤3000
输出
消除字符串所得到的最大得分

样例
输入复制
AABABBB
输出复制
16
输入复制
BABA
输出复制
7
输入复制
BBAA
输出复制
5
提示
如样例一，AABABBB，消除AABABBB→AABBB→ABB→B，最后将B消除，最终得分为5+5+5+1=16

#include <stdio.h>
#include <assert.h>

size_t foo( char* s )
{
    size_t result = 0;

    char* p = s;
    char* q = s;
    for( char* t=s; *t; ++t )
    {
        if( p!=s && p[-1]=='A' && *t=='B' )
        {
            result += 5;
            --p;
        }
        else
        {
            *p = *t;
            ++p;

            if( *t == 'B' ) // 消去所有AB后，余下的字符串必然是 BBB...BAAA...A，因此只需要记录最后一个B的位置即可
                q = p;
        }
    }
    result += (q-s)/2*3 + (q-s)%2*1 + (p-q)*1;
    return result;
}

int main( void )
{
    {
        char s[] = "AABABBB";
        assert( foo(s) == 16 );
    }
    {
        char s[] = "BABA";
        assert( foo(s) == 7 );
    }
    {
        char s[] = "BBAA";
        assert( foo(s) == 5 );
    }
}

算法写复杂了，既然“消去所有AB后，余下的字符串必然是 BBB...BAAA...A”，那么

#include <stdio.h>
#include <assert.h>

unsigned foo( const char* s )
{
    unsigned result = 0;

    unsigned a_cnt=0, b_cnt=0;
    for( const char* p=s; *p; ++p )
    {
        if( *p == 'A' )
            ++a_cnt;
        else if( a_cnt != 0 )
            --a_cnt, result+=5;
        else
            ++b_cnt;
    }

    return result + b_cnt/2*3 + b_cnt%2*1 + a_cnt*1;
}

int main( void )
{
    assert( foo("AABABBB") == 16 );
    assert( foo("BABA") == 7 );
    assert( foo("BBAA") == 5 );
}

[此贴子已经被作者于2022-11-14 13:19编辑过]