MATHHEW

導(dǎo)航

公告

hihoCoder#1039

剛開始學(xué)習(xí)C語言，準(zhǔn)備在做hiho的題目的過程中來學(xué)習(xí)，在此進(jìn)行記錄，如果代碼中有錯(cuò)誤或者不當(dāng)?shù)牡胤竭€請(qǐng)指正。

時(shí)間限制:1000ms

單點(diǎn)時(shí)限:1000ms

內(nèi)存限制:256MB

描述

小Hi最近在玩一個(gè)字符消除游戲。給定一個(gè)只包含大寫字母"ABC"的字符串s，消除過程是如下進(jìn)行的：

1)如果s包含長(zhǎng)度超過1的由相同字母組成的子串，那么這些子串會(huì)被同時(shí)消除，余下的子串拼成新的字符串。

　　例如"ABCCBCCCAA"中"CC","CCC"和"AA"會(huì)被同時(shí)消除，余下"AB"和"B"拼成新的字符串"ABB"。

2)上述消除會(huì)反復(fù)一輪一輪進(jìn)行，直到新的字符串不包含相鄰的相同字符為止。例如”ABCCBCCCAA”經(jīng)過一輪消除得

　　到"ABB"，再經(jīng)過一輪消除得到"A"

游戲中的每一關(guān)小Hi都會(huì)面對(duì)一個(gè)字符串s。在消除開始前小Hi有機(jī)會(huì)在s中任意位置(第一個(gè)字符之前、最后一個(gè)字符之

后以及相鄰兩個(gè)字符之間)插入任意一個(gè)字符('A','B'或者'C')，得到字符串t。t經(jīng)過一系列消除后，小Hi的得分是消除掉

的字符的總數(shù)。

請(qǐng)幫助小Hi計(jì)算要如何插入字符，才能獲得最高得分。

輸入

輸入第一行是一個(gè)整數(shù)T(1<=T<=100)，代表測(cè)試數(shù)據(jù)的數(shù)量。

之后T行每行一個(gè)由'A''B''C'組成的字符串s，長(zhǎng)度不超過100。

輸出

對(duì)于每一行輸入的字符串，輸出小Hi最高能得到的分?jǐn)?shù)。

提示

第一組數(shù)據(jù)：在"ABCBCCCAA"的第2個(gè)字符后插入'C'得到"ABCCBCCCAA"，消除后得到"A"，總共消除9個(gè)字符(包括插入的'C')。

第二組數(shù)據(jù)："AAA"插入'A'得到"AAAA"，消除后得到""，總共消除4個(gè)字符。

第三組數(shù)據(jù)：無論是插入字符后得到"AABC","ABBC"還是"ABCC"都最多消除2個(gè)字符。

解決思路

對(duì)各個(gè)位置進(jìn)行循環(huán)插入'A','B','C'計(jì)算得到分?jǐn)?shù)如果分?jǐn)?shù)比之前的分?jǐn)?shù)高的話就取代前面的分?jǐn)?shù)，如果有能夠把所有字符都消除的方法

即得分達(dá)到輸入的字符串個(gè)數(shù)加一時(shí)則停止。最后輸出分?jǐn)?shù)。

獲取分?jǐn)?shù)就是獲取消除后最少能剩下的個(gè)數(shù)。獲取消除后個(gè)數(shù)的方法：對(duì)字符串進(jìn)行消除，每次將有兩個(gè)或兩個(gè)以上連續(xù)的相同字符消

除掉，直到不存在連續(xù)兩個(gè)相同的字符。

#include<stdio.h>

int GetScore(char str[]);
int GetNumAftElim(char str[]);

int main()
{
    int n,i,*Score;
    char str[101];
    scanf("%d",&n);
    Score=(int*)malloc(n*sizeof(int));
    for(i=0;i<n;i++)
    {
        scanf("%s",&str);
        Score[i]=GetScore(str);
    }
    for(i=0;i<n;i++)
    {
    printf("%d\n",Score[i]);
    }
    free(Score);
    return 0;
}

int GetScore(char str[])
{
    int i,j,k,NumAftElim=101,NumA_l;
    char Istr[101];
    for(j='A';j<='C';j++)
    {
        for(i=0;str[i];i++)
        {
            for(k=0;k<i;k++)
            Istr[k]=str[k];
            Istr[i]=(char)j;
            for(k=i;str[k];k++)
            Istr[k+1]=str[k];
            Istr[k+1]=str[k];
            NumA_l=GetNumAftElim(Istr);
            if(NumAftElim>NumA_l)
            NumAftElim=NumA_l;
            if(NumAftElim==0)
            break;
        }
        if(NumAftElim==0)
        break;
    } 
    for(i=0;str[i];i++)
    {}
    return i+1-NumAftElim;
}

int GetNumAftElim(char str[])
{
    int i=1,j,k,count=0;
    char c='0';
    while(i)
    {
        i=0;k=0;c='0';
        for(j=0;str[j];j++)
        {
            if((int)c=='0')
            c=str[j];
            else if((int)c==(int)str[j])
                 {
                     count++;
                     i=1;
                 }
                 else if(count==0)
                      {
                      　　str[k++]=c;
                      　　c=str[j];
                      }
                      else
                      {
                      　　count=0;
                      　　c=str[j]; 
                      }
        }
        if(count==0)
        str[k++]=str[j-1];
        else
        count=0; 
        str[k]=0;
    }
    for(i=0;str[i];i++)
    {}
    return i;
}

posted on 2015-10-02 20:56 MATHHEW 閱讀(546) 評(píng)論(0) 收藏舉報(bào)

刷新頁面返回頂部