CFR 191 A. Dynasty Puzzles ( DP )

Problem - A - Codeforces

題意：
給有序的名字表。求最長的字串長度，字串須能拆解成名字表裡的字，且順序須依照表中的順序，且連接的兩個字串，前面字串字尾需與後面字串字頭相同。最後的字串必須滿足字頭與字尾相等。

數據範圍：
字串數 1 ≤ N ≤ 5e5
字串長度 1 ≤ S[ i ] ≤ 10
字串皆由小寫英文字母組成

解法：
dp[ i ][ j ] : 以 'a' + i 開頭，且以 'a' + j 結尾的最終字串最長長度。
答案便是 max{ dp[ i ][ i ] }

時間 / 空間複雜度：
O( N * 26 ) / O( 26 * 26 )

需要注意：
第 17、18 行，如果不將 size 手動轉型，由於前面的整數是負值，編譯器自動轉型會溢位爛掉!!!!!

p.s. #define SZ( x ) が使いたくなった。。。でも堪えるぞ

int N;
vs name;

void init(){
    cin >> N;
    name = vs( N );
    for( int i = 0; i < N; ++i )
        cin >> name[ i ];
}

vvi dp;

void preprocess(){
    dp = vvi( 26, vi( 26, -INF ) );
    for( int i = 0; i < N; ++i ){
        for( int j = 0; j < 26; ++j )
            upmax( dp[ j ][ name[ i ][ name[ i ].size() - 1 ] - 'a' ], dp[ j ][ name[ i ][ 0 ] - 'a' ] + ( int ) name[ i ].size() );
        upmax( dp[ name[ i ][ 0 ] - 'a' ][ name[ i ][ name[ i ].size() - 1 ] - 'a' ], ( int ) name[ i ].size() ); // ^^<<SEE WHAT WILL HAPPEN WITHOUT ( int )
    }
}

void solve(){
    int ans = 0;
    for( int i = 0; i < 26; ++i )
        upmax( ans, dp[ i ][ i ] );
    cout << ans << endl;
}