7.9単語ゲーム検索

7.9単語ゲーム
ソースプログラム名words???(pas,c,cpp)実行可能ファイル名words.exeファイル名wordsを入力します.Inファイル名wordsを出力する.out
【問題の説明】
IoとAoは単語ゲームをしています.
彼らは順番にアクセントアルファベットのみを含む単語を話し、後の単語の最初のアルファベットは前の単語の最後のアルファベットと一致しなければならない.
ゲームはどの単語からでも開始できます.
どの単語も2回は禁止されており、ゲームでは所定の辞書に含まれている単語しか使用できません.
ゲームの複雑さは、ゲームで使用される単語の長さの合計として定義されます.
プログラムを作成し,与えられた辞書を用いてこのゲームをプレイすることで達成できるゲームの最大の複雑さを求める.
【入力】
入力ファイルの最初の行は、自然数N(1≦N≦16)を表し、Nは辞書に含まれる単語の数以下の行ごとに辞書に含まれる単語を表し、各単語はアルファベットA、E、I、O、Uからなる文字列であり、各単語の長さは100以下であり、すべての単語は異なる.
【出力】
出力ファイルは1行のみで、ゲームの最大の複雑さを示します.
【例】
       words.in                                            words.out
       5                                                      16
       IOO
       IUUO
       AI
       OIOOI
       AOOI
【問題分析】
取りたい単語を列挙し,この単語構成の図にオーラル(必ずしもループではない)が存在すると,これらの単語の長さと解が1つの単語に引き継がれるスキームが存在する.答えはすべての解の最大値です.アルゴリズムの時間的複雑さはO(2 n・n),n≦16であった.
 

PROGRAM words;
CONST
    maxrijeci=100;
    maxdulj=100;
VAR
    n:integer;
    nrijec:ARRAY[1..5, 1..5] OF integer;
    dulj:ARRAY[1..5, 1..5, 1..maxrijeci] OF integer;

FUNCTION num(c:char):integer;
BEGIN
    CASE c OF
        'A':num:=1;
        'E':num:=2;
        'I':num:=3;
        'O':num:=4;
        'U':num:=5;
    END;
END;

PROCEDURE citaj_ulaz;
VAR fin:text;
    i, j, k, l, t:integer;
    tmp:STRING[maxdulj];
    prvi, zadnji:integer;

BEGIN
    FOR i:=1 TO 5 DO
        FOR j:=1 TO 5 DO
            nrijec[i, j]:=0;
    assign(fin, 'WORDS.in');
    reset(fin);
    readln(fin, n);
    FOR i:=1 TO n DO
    BEGIN
        readln(fin, tmp);
        prvi:=num(tmp[1]);
        zadnji:=num(tmp[length(tmp)]);
        inc(nrijec[prvi, zadnji]);
        dulj[prvi, zadnji, nrijec[prvi, zadnji]]:=length(tmp);
    END;
    close(fin);
    { Sortiram rijeci po duljini }
    FOR i:=1 TO 5 DO
        FOR j:=1 TO 5 DO
            FOR k:=1 TO nrijec[i, j]-1 DO
                FOR l:=k+1 TO nrijec[i, j] DO
                    IF dulj[i, j, k]>dulj[i, j, l] THEN
                    BEGIN
                        t:=dulj[i, j, k];
                        dulj[i, j, k]:=dulj[i, j, l];
                        dulj[i, j, l]:=t;
                    END;
END;

FUNCTION nadji (zadnji:integer):integer;
VAR i:integer;
    max:integer;
    tmp:integer;
BEGIN
    max:=0;
    FOR i:=1 TO 5 DO
        IF nrijec[zadnji, i]>0 THEN
        BEGIN
            dec(nrijec[zadnji, i]);
            tmp:=dulj[zadnji, i, nrijec[zadnji, i]+1]+nadji(i);
            inc(nrijec[zadnji, i]);
            IF tmp>max THEN max:=tmp;
        END;
    nadji:=max;
END;

PROCEDURE rijesi;
VAR fout:text;
    i:integer;
    max, tmp:integer;
BEGIN
    max:=0;
    FOR i:=1 TO 5 DO
    BEGIN
        tmp:=nadji(i);
        IF (tmp>max) THEN max:=tmp;
    END;
    assign(fout, 'WORDS.out');
    rewrite(fout);
    writeln(fout, max);
    close(fout);
END;

{ Glavni program }
BEGIN
    citaj_ulaz;
    rijesi;
END.