CFR 706 C. Hard problem ( DP )

Problem - C - Codeforces
很簡單的DP。
dp[ i ][ j ] : minimum cost for already determined i strings, last string reversed ( or not -> j = 0 )

bool ok( string s1, string s2 ){
    return s1 <= s2;
}

void solve(){
    int N; cin >> N;
    vi C( N );
    for( int i = 0; i < N; ++i )
        cin >> C[ i ];
    vector< string > dict( N );
    for( int i = 0; i < N; ++i )
        cin >> dict[ i ];

    vvi dp( N + 1, vi( 2, INF ) );
    dp[ 1 ][ 0 ] = 0, dp[ 1 ][ 1 ] = C[ 0 ];

    for( int i = 1; i < N; ++i )
        for( int j = 0; j < 2; ++j )
            if( dp[ i ][ j ] < INF ){
                string a = dict[ i - 1 ];
                if( j ) reverse( a.begin(), a.end() );
                string b = dict[ i ];

                if( ok( a, b ) )
                    upmin( dp[ i + 1 ][ 0 ], dp[ i ][ j ] );

                reverse( b.begin(), b.end() );
                if( ok( a, b ) )
                    upmin( dp[ i + 1 ][ 1 ], dp[ i ][ j ] + C[ i ] );
            }

    ll ans = min( dp[ N ][ 0 ], dp[ N ][ 1 ] );
    if( ans == INF ) cout << -1 << "\n";
    else cout << ans << "\n";
}