这道题第一眼直接一个二分板子把第一问解决掉,然后主要是统计方案。
其实这个方程还不算难推,只要推出来朴素 \(dp\) ,之后的一步一步也很顺理成章,所以这种题主要看能不能静下心来慢慢做。
solution
第一问就是一个 Monthly Expense S ,本片题解只说第二问。
朴素 \(dp\)
也没几个变量,所以很轻松的可以设计状态 \(f[i][j]\) 表示当前到第 \(i\) 段,一共分了 \(j\) 次的方案数。
我们思考如何来表示把几段放在一大段里面,也就可以推出来转移方程。
如果我们新开一段,那么 \(f[i][j] += f[i-1][j-1]\)
如果我们把这段和上一段拼到一起,那么 \(f[i][j] += f[i - 1][j - 1]\)
以此类推,规律很显然,所以可以写出 \(dp\) 方程。
\]
能从 \(k\) 转移的要求是从 \(k\) 加到 \(i\) 的木棍长度不大于第一问的答案 。
其实 \(dp\) 方程没有那么难推,只要设计好状态分情况讨论就行了。
时间复杂度是 \(O(n^2m)\) ,因为 \(k\) 需要枚举。
显然时间空间都不行,所以考虑优化。
空间优化
这个不难想到,因为 \(f [i][j]\) 只能有 \(f[k][j-1]\) 转移而来,所以我们调换一下维数顺序和枚举顺序就行,用第一维来表示分了 \(i\) 次,第二维来表示到第 \(i\) 段。
然后就能滚动数据优化了,空间问题就解决了(其实开short
也勉强不爆)
时间优化
首先,我们可以发现,对于一个 \(f[i][j]\) ,能转移到他的 \(f[i-1][k]\) 中的 \(k\) 肯定是连续的一段,并且最小的 \(k\) 的值之和 \(i\)有关。
所以我们可以考虑预处理出来 \(k\) 的值,然后直接一个前缀和解决问题。
不过处理 \(k\) 需要 \(n^2\) ,怎么办?
不难发现随着 \(i\) 的增加, \(k\) 是单调不降的,弄个单调指针就行了,均摊 \(O(n)\) 。
所以最后复杂度是 \(O(nm+n)=O(nm)\)
code
(放这么丑的代码真是对不起大家的眼睛啦)
#include <cstring>
#include <algorithm>
#include <cstdio>
#define mp make_pair
#define R register int
#define int long
#define printf Ruusupuu = printf
int Ruusupuu ;
using namespace std ;
typedef long long L ;
typedef long double D ;
typedef unsigned long long G ;
typedef pair< int , int > PI ;
const int N = 5e4 + 10 ;
const int M = 1e3 + 10 ;
const int P = 1e4 + 7 ;
inline int read(){
int w = 0 ; bool fg = 0 ; char ch = getchar() ;
while( ch < '0' || ch > '9' ) fg |= ( ch == '-' ) , ch = getchar() ;
while( ch >= '0' && ch <= '9' ) w = ( w << 1 ) + ( w << 3 ) + ( ch ^ '0' ) , ch = getchar() ;
return fg ? -w : w ;
}
inline int J( int a , int b ){ return a + b >= P ? a + b - P : a + b ; }
inline int S( int a , int b ){ return a - b < 0 ? a - b + P : a - b ; }
int len [N] , n , m , mid , lside , rside , ans , pre [N] , f [3][N] , qz [3][N] , res ;
void sc(){
n = read() , m = read() ;
for( R i = 1 ; i <= n ; i ++ ) len [i] = read() , lside = max( lside , len [i] ) ;
}
bool check(){
int div = 0 , now = 0 ;
for( R i = 1 ; i <= n ; i ++ ){
if( now + len [i] > mid ) div ++ , now = 0 ;
now += len [i] ;
}// printf( "%ld %ld\n" , mid , div ) ;
return div <= m ;
}
void work(){
rside = (int) 5e7 + 10 , ans = 0 ;
while( lside <= rside ){
mid = ( lside + rside ) >> 1 ;
if( check() ) ans = mid , rside = mid - 1 ;
else lside = mid + 1 ;
} printf( "%ld " , ans ) ;
int now = 0 , ck = 0 ;
for( R i = 1 ; i <= n ; i ++ ){
now += len [i] ;
while( now > ans ) now -= len [ck ++] ;
pre [i] = ck - 2 ; //printf( "%ld\n" , pre [i] ) ;
}
f [0][0] = 1 ;
for( R i = 0 ; i <= n ; i ++ ) qz [0][i] = 1 ;
for( R i = 1 ; i <= m + 1 ; i ++ ){
for( R j = 1 ; j <= n ; j ++ ){
if( pre [j] == -2 ) f [i & 1][j] = qz [( i - 1 ) & 1][j - 1] ;
else f [i & 1][j] = S( qz [( i - 1 ) & 1][j - 1] , qz [( i - 1 ) & 1][pre [j]] ) ;
qz [i & 1][j] = J( qz [i & 1][j - 1] , f [i & 1][j] ) ;
// printf( "%ld %ld %ld %ld\n" , i , j , f [i & 1][j] , qz [i & 1][j] ) ;
}
for( R j = 0 ; j <= n ; j ++ ) f [( i - 1 ) & 1][j] = qz [( i - 1 ) & 1][j] = 0 ;
res = J ( res , f [i & 1][n] ) ;
}
printf( "%ld\n" , res ) ;
}
signed main(){
sc() ;
work() ;
return 0 ;
}