BZOJ-3304: [Shoi2005]带限制的最长公共子序列

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3304

LCS的变种，虽然不难，但是细节挺多的，而且要滚动数组才能过。

代码：

a2cc7cd98d1001e983229e7cba0e7bec54e797a3.jpg.png

#include <cstdio>
#include <algorithm>
#include <cstring>
 
using namespace std ;
 
#define MAXN 510
 
char s0[ MAXN ] , s1[ MAXN ] , s2[ MAXN ] ;
int n , m , w , f[ 2 ][ MAXN ][ MAXN ] , h = 0 , ans = 0 ;
 
int main(  ) {
    scanf( "%s%s%s" , s0 + 1 , s1 + 1 , s2 + 1 ) ;
    n = strlen( s0 + 1 ) , m = strlen( s1 + 1 ) , w = strlen( s2 + 1 ) ;
    f[ 0 ][ 0 ][ 0 ] = 0 ; 
    for ( int i = 0 ; i ++ < n ; ) {
        for ( int j = 0 ; j ++ < m ; ) for ( int k = 0 ; k <= w ; k ++ ) {
            f[ h ^ 1 ][ j ][ k ] = max( max( f[ h ][ j ][ k ] , f[ h ^ 1 ][ j - 1 ][ k ] ) , f[ h ][ j - 1 ][ k ] );
            if ( s0[ i ] == s1[ j ] ) {
                if ( f[ h ][ j - 1 ][ k ] || k == 0 ) f[ h ^ 1 ][ j ][ k ] = max( f[ h ^ 1 ][ j ][ k ] , f[ h ][ j - 1 ][ k ] + 1 ) ;
                if ( s0[ i ] == s2[ k ] && ( f[ h ][ j - 1  ][ k - 1 ] || ( k - 1 ) == 0 ) ) {
                    f[ h ^ 1 ][ j ][ k ] = max( f[ h ^ 1 ][ j ][ k ] , f[ h ][ j - 1 ][ k - 1 ] + 1 ) ;
                }
            }
        }
        for ( int j = 0 ; j ++ < m ; ) ans = max( ans , f[ h ^ 1 ][ j ][ w ] ) ;
        h ^= 1 ;
    }
    if ( ans - 1 > 0 ) printf( "%d\n" , ans ) ; else printf( "NO SOLUTION\n" ) ;
    return 0 ;
}