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
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 ;
}