BZOJ-1044: [HAOI2008]木棍分割（二分+贪心+

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

第一问用二分+贪心很好解决就不说了，设第一问答案为ANS0

第二问DP，令f[ i ][ j ]表示砍了i次，最后一次砍在j这个地方的方案数，那么f[ i ][ j ] = sigma( f[ i - 1 ][ k ] ) ( dist( k , j ) <= ANS0 , k < j ) ， 然后我们发现k范围的左区间是递增的，那么用一个变量O( 1 )维护sigma( f[ i - 1 ][ k ] )，接下来滚动数组节省一下空间就可以O（NM）啦。

代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
 
using namespace std ;
 
const int maxn = 50010 , maxm = 1010 , mod = 10007 ;
 
int a[ maxn ] , ans0 , n , m , sum = 0 , pre[ maxn ] ;
 
bool check( int x ) {
    int cnt = 1 , rec = 0 ; 
    for ( int i = 0 ; i ++ < n ; ) if ( rec + a[ i ] <= x ) {
        rec += a[ i ] ;
    } else {
        if ( a[ i ] > x ) return false ;
        rec = a[ i ] , cnt ++ ; 
    }
    return cnt <= m + 1 ;
}
 
int solve0(  ) {
    int l = 0 , r = sum , mid ; 
    while ( r - l > 1 ) {
        mid = ( l + r ) >> 1 ; 
        if ( check( mid ) ) r = mid ; else l = mid ;
    }
    return r ; 
}
 
int f[ 2 ][ maxn ] , k = 0 ; 
 
void update( int &val , int delta ) {
    val = ( val + delta + mod ) % mod ;
}
 
int dp(  ) {
    memset( f[ 0 ] , 0 , sizeof( f[ 0 ] ) ) ;
    f[ 0 ][ 0 ] = 1 ; 
    int ans1 = 0 ; 
    for ( int i = 0 ; i ++ < m ; ) {
        int temp = f[ k ][ 0 ] , pos = 0 ; 
        memset( f[ k ^ 1 ] , 0 , sizeof( f[ k ^ 1 ] ) ) ;
        for ( int j = 1 ; j < n ; ++ j ) {
            for ( ; pre[ j ] - pre[ pos ] > ans0 ; update( temp , - f[ k ][ pos ++ ] ) ) ;
            if ( j - 1 ) update( temp , f[ k ][ j - 1 ] ) ;
            f[ k ^ 1 ][ j ] = temp ;
            if ( pre[ n ] - pre[ j ] <= ans0 ) update( ans1 , temp ) ;
        }
        k ^= 1 ;
    }
    return ans1 + ( pre[ n ] <= ans0 ) ;
}
 
int main(  ) {
    scanf( "%d%d" , &n , &m ) ;
    pre[ 0 ] = 0 ;
    for ( int i = 0 ; i ++ < n ; ) {
        scanf( "%d" , a + i ) ;
        sum += a[ i ] , pre[ i ] = pre[ i - 1 ] + a[ i ] ;
    }
    printf( "%d " , ans0 = solve0(  ) ) ;
    printf( "%d\n" , dp(  ) ) ;
    return 0 ; 
}