[BZOJ1044][HAOI2008]木棍分割二分 + 单调队列优化dp + 滚动数组优化dp

Description

　　有n根木棍, 第i根木棍的长度为Li,n根木棍依次连结了一起, 总共有n-1个连接处. 现在允许你最多砍断m个连
接处, 砍完后n根木棍被分成了很多段,要求满足总长度最大的一段长度最小, 并且输出有多少种砍的方法使得总长
度最大的一段长度最小. 并将结果mod 10007。。。

Input

　　输入文件第一行有2个数n,m.接下来n行每行一个正整数Li,表示第i根木棍的长度.n<=50000,0<=m<=min(n-1,10
00),1<=Li<=1000.

Output

　　输出有2个数, 第一个数是总长度最大的一段的长度最小值, 第二个数是有多少种砍的方法使得满足条件.

Sample Input

3 2
1
1
10

Sample Output

10 2

HINT

两种砍的方法: (1)(1)(10)和(1 1)(10)

Solution

做法：二分+单调队列优化+滚动数组优化

第一问直接二分答案然后暴力$check$一下就行了，套路

第二问的话呢，用$dp$来求出答案

可以设$f[i][j]$表示前$i$个木棍切成$j$段时最大长度不大于第一问的$ans$的方案数

那么$$f[i][j]=\sum_{k}^{k<=i}f[k][j-1](sum[i]-sum[k-1]>=ans1)$$

那个$sum$前缀和一下就可以了

然而$dp$空间爆炸，但是可以发现切成$j$个时只会从$j-1$转移过来，所以滚动掉$j$这一维

然后就会发现时间爆炸，不过可以发现对于每个$i$，转移的$k$是固定的，所以拿个单调队列扫一扫就行了

#include <bits/stdc++.h>

using namespace std ;

#define N 100010

#define inf 0x3f3f3f3f

#define mod 10007

int n , m ;

int a[ N ] , f[  ][ N ] , q[ N ] , sum[ N ] ;

bool check( int x ) {

    int sum =  , cnt =  ;

    for( int i =  ; i <= n ; i ++ ) {

        if( sum + a[ i ] > x ) sum =  , cnt ++ ;

        sum += a[ i ] ;

        if( a[ i ] > x ) return  ;

        if( cnt > m ) return  ;

    }

    return  ;

}

int main() {

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

    int l = inf , r , ans ;

    for( int i =  ; i <= n ; i ++ ) {

        scanf( "%d" , &a[ i ] ) ;

        l = min( l , a[ i ] ) ;

        sum[ i ] = sum[ i -  ] + a[ i ] ;

    }

    r = sum[ n ] ;

    while( l <= r ) {

        int mid = ( l + r ) >>  ;

        if( check( mid ) ) ans = mid , r = mid -  ;

        else l = mid +  ;

    }

    printf( "%d " , ans ) ;

    f[  ][  ] =  ;

    int ans2 =  ;

    for( int i =  ; i <= m ; i ++ ) {

        int pre = i& , cur = pre^ , tot = f[ cur ][  ] ;

        l =  , r =  ;

        q[  ] =  ;

        for( int j =  ; j <= n ; j ++ ) {

            while( l <= r && sum[ j ] - sum[ q[ l ] ] > ans )

                tot = ( tot - f[ cur ][ q[ l ++ ] ] + mod ) % mod ;

            f[ pre ][ j ] = tot ;

            q[ ++ r ] = j ;

            tot = ( tot + f[ cur ][ j ] + mod ) % mod ;

        }

        for( int j = n -  ; j ; j -- ) {

            if( sum[ n ] - sum[ j ] > ans ) break ;

            ans2 = ( ans2 + f[ pre ][ j ] + mod ) % mod ;

        }

        memset( f[ cur ] ,  , sizeof( f[ cur ] ) ) ;

    }

    printf( "%d\n" , ans2 ) ;

    return  ;

}

巴特西

[BZOJ1044][HAOI2008]木棍分割二分 + 单调队列优化dp + 滚动数组优化dp

Description

Input

Output

Sample Input

Sample Output

HINT

Solution

做法：二分+单调队列优化+滚动数组优化

最新文章

热门文章

巴特西

[BZOJ1044][HAOI2008]木棍分割 二分 + 单调队列优化dp + 滚动数组优化dp

Description

Input

Output

Sample Input

Sample Output

HINT

Solution

做法：二分+单调队列优化+滚动数组优化

最新文章

热门文章

[BZOJ1044][HAOI2008]木棍分割二分 + 单调队列优化dp + 滚动数组优化dp