題目：http://www.lydsy.com/JudgeOnline/problem.php?id=3042
方程：
f[ i ][ j ][ 0 ] = max( f[ i - 1 ][ j ][ 0 ] , f[ i - 1 ][ j ][ 1 ] )
f[ i ][ j ][ 1 ] = max( f[ i - 1 ][ j - 1 ][ 1 ] + u i , f[ i - 1 ][ j - 1 ][ 0 ] )
然后第一次令f[ 1 ][ 0 ][ 0 ] = f[ 1 ][ 1 ][ 1 ] = 0 对省，目標(biāo)狀態(tài)f[ n ][ m ][ 0 ] , f[ n ][ m ][ 1 ]
然后再令f[ 1 ][ 1 ][ 1 ] = u[ 1 ] ,再做一次DP饼暑，目標(biāo)狀態(tài)f[ n ][ min( n - 1 , m ) ][ 1 ]
代碼：
include <cstdio>
include <algorithm>
include <cstring>
using namespace std ;
define MAXN 4010
define inf 0x7fffffff
int f[ MAXN ][ MAXN ][ 2 ] , n , m , u[ MAXN ] , ans = - inf ;
int main( ) {
scanf( "%d%d" , &n , &m ) ; for ( int i = 0 ; i ++ < n ; ) scanf( "%d" , &u[ i ] ) ;
for ( int i = 0 ; i ++ < n ; ) for ( int j = 0 ; j <= m ; j ++ ) f[ i ][ j ][ 0 ] = f[ i ][ j ][ 1 ] = - inf ;
f[ 1 ][ 0 ][ 0 ] = f[ 1 ][ 1 ][ 1 ] = 0 ;
for ( int i = 1 ; i ++ < n ; ) {
for ( int j = 0 ; j <= m ; j ++ ) {
f[ i ][ j ][ 0 ] = max( f[ i - 1 ][ j ][ 1 ] , f[ i - 1 ][ j ][ 0 ] ) ;
if ( j ) f[ i ][ j ][ 1 ] = max( f[ i - 1 ][ j - 1 ][ 1 ] + u[ i ] , f[ i - 1 ][ j - 1 ][ 0 ] ) ;
}
}
ans = max( ans , max( f[ n ][ m ][ 0 ] , f[ n ][ m ][ 1 ] ) ) ;
for ( int i = 0 ; i ++ < n ; ) for ( int j = 0 ; j <= m ; j ++ ) f[ i ][ j ][ 0 ] = f[ i ][ j ][ 1 ] = - inf ;
f[ 1 ][ 1 ][ 1 ] = u[ 1 ] ;
for ( int i = 1 ; i ++ < n ; ) {
for ( int j = 0 ; j <= m ; j ++ ) {
f[ i ][ j ][ 0 ] = max( f[ i - 1 ][ j ][ 1 ] , f[ i - 1 ][ j ][ 0 ] ) ;
if ( j ) f[ i ][ j ][ 1 ] = max( f[ i - 1 ][ j - 1 ][ 1 ] + u[ i ] , f[ i - 1 ][ j - 1 ][ 0 ] ) ;
}
}
ans = max( ans , f[ n ][ min( n - 1 , m ) ][ 1 ] ) ;
printf( "%d\n" , ans ) ;
return 0 ;
}
