BZOJ-1786: [Ahoi2008]Pair 配对 &am

题目：

http://www.lydsy.com/JudgeOnline/problem.php?id=1786

http://www.lydsy.com/JudgeOnline/problem.php?id=1831

我们可以神奇的证明出填入的数是单调不递减的（证明详解灰天飞雁大神的神题解：http://www.cnblogs.com/htfy/archive/2012/12/11/2813497.html），于是乎我们就可以很愉快的DP出来了。

代码：

#include <cstdio>

#include <algorithm>

#include <cstring>

 

using namespace std ;

 

#define Rep( i , x ) for ( int i = 0 ; i < x ; ++ i )

#define rep( i , x ) for ( int i = 0 ; i ++ < x ; )

#define REP( i , l , r ) for ( int i = l ; i <= r ; ++ i )

 

const int maxn = 10010 , maxk = 110 , inf = 1000000000 ;

 

int dp[ maxn ][ maxk ] , pre[ maxn ][ maxk ] , a[ maxn ] , n , k , ans = 0 ;

 

int Count( int pos , int val ) {

    return ( pre[ pos ][ k ] - pre[ pos ][ val ] ) + ( pre[ n ][ val - 1 ] - pre[ pos ][ val - 1 ] ) ;

}

 

int main(  ) {

    memset( pre[ 0 ] , 0 , sizeof( pre[ 0 ] ) ) ;

    scanf( "%d%d" , &n , &k ) ;

    rep( i , n ) {

        scanf( "%d" , a + i ) ;

        REP( j , 0 , k ) pre[ i ][ j ] = pre[ i - 1 ][ j ] ;

        if ( a[ i ] != -1 ) ++ pre[ i ][ a[ i ] ] ;

    }

    rep( i , n ) rep( j , k ) pre[ i ][ j ] += pre[ i ][ j - 1 ] ;

    rep( i , n ) {

        if ( a[ i ] != -1 ) ans += ( pre[ i ][ k ] - pre[ i ][ a[ i ] ] ) ;

    }

    rep( i , k ) dp[ 0 ][ i ] = inf ;

    dp[ 0 ][ 1 ] = 0 ;

    int last = 0 , temp ;

    rep( i , n ) if ( a[ i ] == -1 ) {

        rep( j , k ) {

            temp = inf ;

            rep( h , j ) temp = min( temp , dp[ last ][ h ] ) ;

            dp[ i ][ j ] = min( inf , temp + Count( i , j ) ) ;

        }

        last = i ;

    }

    temp = inf ;

    rep( j , k ) temp = min( temp , dp[ last ][ j ] ) ;

    printf( "%d\n" , ans + temp ) ;

    return 0 ;

}