2016年ブルーブリッジカップA組第9題パスワード脱落

X星の考古学者は古代に残された暗号を発見した.これらの暗号はA,B,C,Dの4種類の植物の種子からなる配列である.よく分析すると、これらの暗号列は当初前後対称であるべきである(すなわち、私たちが言ったミラー列である).年代が古いため、多くの種が脱落し、ミラーの特徴を失う可能性があります.
あなたの任務は:今見ている暗号列を与えて、当初の状態から、少なくとも何個の種が抜けてこそ、今の姿になる可能性があるかを計算することです.
現在表示されている暗号列(長さ1000以下)に正の整数を出力する必要があることを示す行を入力し、少なくともどれだけのシードが脱落したかを示します.
例えば、入力:ABCBAはプログラム出力:0
例えば、入力:ABECDCBABC則プログラム出力:3
リソース約定:ピークメモリ消費<256 M CPU消費<1000 ms
要求通りに出力し、「入力してください」のような余分な内容を蛇足せずに印刷してください.
すべてのコードを同じソースファイルに配置し、デバッグに合格した後、コピーしてソースコードをコミットします.
注意:main関数は0を返す必要があります注意:ANSI C/ANSI C++標準のみを使用し、コンパイル環境やオペレーティングシステムに依存する特殊な関数を呼び出さないでください.注意:すべての依存する関数は、ソースファイル内のincludeで明確にする必要があります.通常のヘッダファイルは、エンジニアリング設定で省略することはできません.
文字列の処理の問題の上で、私は弱点で、この問題を見て、構想がないことに苦しんで、何度も探して、構想を見つけて、そしてCコードで実現して、これらのタイプの問題を覚えることができることを望みます.
コードC:

#include <stdio.h>
#include <string.h>
void code(char *s)
{
    int i = 0, n = 0, ti, tj;
    int j = (int)strlen(s) - 1;

    while (i <= j)
    {
        //            ，      
        if (s[i] == s[j])
        {
            i++;
            j--;
        }
        //             
        else
        {
            ti = i;
            tj = j;
            //                    
            while (s[ti] != s[j] && ti < j)
            {
                ti++;
            }
            //                    
            while (s[i] != s[tj] && i <= tj)
            {
                tj--;
            }
            //           ，     
            if ((ti - i) < (j - tj))
            {
                n += ti - i;
                i = ti;     // i      
            }
            else
            {
                n += j - tj;
                j = tj;     // j      
            }
        }
    }
    printf("%d
", n);
    return ;
}

int main(int argc, const char * argv[])
{
    char s[1000];
    scanf("%s", s);
    //    
    code(s);
    return 0;
}

難しそうな問題ですが、(実は本当に難しいですが、私のような類型の問題をしたことがない人にとっては、完全に萌え状態です)、最後に使った方法はこんなに効率的で、複雑度はO(n^2)だけで、これは予想外で、アルゴリズムのすばらしさに感心せられました(もちろん感心したわけではありません).
同じように素晴らしい解法を書いて、人を感嘆させる解法を書きます!コードC:

#include <stdio.h>
#include <string.h>
char s[1000];
int min = 0, num = 0;

void fcode(int left, int right, int num)
{
    if (left >= right)
    {
        min = min < num ? min : num;
    }
    else
    {
        if (s[left] == s[right])
        {
            fcode(left + 1, right - 1, num);
        }
        else
        {
            fcode(left + 1, right, num + 1);
            fcode(left, right - 1, num + 1);
        }
    }
    return ;
}

int main(int argc, const char * argv[])
{
    scanf("%s", s);
    min = (int)strlen(s);
    //    
    fcode(0, min - 1, 0);
    printf("%d
", min);
    return 0;
}

この方法は繰返しを用い,非常に巧みであるが,中心思想は第1のコードと同じであるが,第1のアルゴリズムは貪欲なアルゴリズムとの結合に偏り,時間複雑度は線形であるのに対し,第2のコードは列挙に偏り,時間複雑度は木の形であり,多くの分岐を考慮し,過剰な判断を行い,テストデータが十分に大きい場合,きっと2番目に先に爆発して、しかしその思想は学ぶ価値があって、今日収获はとても大きいです!!!OVER!!!