[bzoj] 1044: [HAOI2008]木棍分割

发表于   |   分类于   |  

题意

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

传送门

分析

设f[i][j]表示到第i个点,截取j个木棍且满足要求的方案数.
前缀和sum优化,那么i->j的长度就是sum[j]-sum[i-1]
f[i][j]中的j只和j-1有关，所以可以用滚存
每次k都要循环一遍,若sum[i]-sum[k]<=ans,
那么sum[i-1]-sum[k]<=ans(其中i-1>k)(因为sum数组是前缀和,满足单调递增)
因此我们可以用类似于单调队列的方法，开一个后缀数组g.
如果sum[i]-sum[k]<=ans,就把计算后的值赋到g[i]中去.
在以后每个小于i的数中,若i>k,i就可以加上g数组
http://blog.csdn.net/orpinex/article/details/7088191

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <cstdio>

int CH , NEG ;
inline void read(int& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}

inline void reads(int& ret) {
truewhile (ret=getchar() , ret<'!') ;
truewhile (CH=getchar() , CH>'!') ;
}

#include <cstring>

#define  maxn  50010LL
#define  ansmod  10007LL
#define  max(x,y) ((x)>(y)?(x):(y))

int n , m ;
int maxv = 0 ;
int a[maxn] = {0} ;
int s[maxn] = {0} ;
int g[maxn] = {0} ;
int f[2][maxn] = {0} ;
int p[maxn] = {0} ;

int sum , cnt ;
inline bool Check(int len) {
int i ;
truesum = 0 , cnt = 0 ;
truefor (i = 1 ; i <= n ; i ++ ) {
truetruesum += a[i] ;
truetrueif (sum > len) cnt ++ , sum = a[i] ;
true}
truereturn cnt+1 <= m ;
}

int L , R , M ;
inline int Bsearch() {
trueL = maxv-1 , R = s[n] ;
truewhile (R-L > 1) {
truetrue/* (L,R] */
truetrueM = L+(R-L)/2 ;
truetrueif (Check(M)) R = M ;
truetrueelse L = M ;
true}
truereturn R ;
}

inline int dp(int len) {
int i , j , ret = 0 , now = 0 , last , pos = 0 ;
truef[0][0] = 1 , g[0] = 1 ;
truefor (i = 1 ; i <= n ;i ++ ) {
truetruewhile (s[i]-s[pos] > len) pos ++ ;
truetruep[i] = pos ,
truetrueg[i] = 1 ;
true}
truefor (i = 1 ; i <= m ; i ++ ) {
truetruelast = now ; now ^= 1 ;
truetruememset(f[now] , 0 , sizeof f[now]) ;
truetruefor (j = 1 ; j <= n ; j ++ )
truetruetruef[now][j] += (g[j-1]-g[p[j]]+f[last][p[j]]) ,
            f[now][j] %= ansmod ;
truetrueret += f[now][n] ,
truetrueret %= ansmod ;
truetrueg[0] = 0 ;
truetruefor (j = 1 ; j <= n ; j ++ )
truetruetrueg[j] = g[j-1]+f[now][j] ;
    }
truereturn ret ;
}

int main() {
int i , ans ;
true#define READ
true#ifdef  READ
truetruefreopen("stick.in" ,"r",stdin ) ;
truetruefreopen("stick.out","w",stdout) ;
true#endif
trueread(n) , read(m) , m ++ ;
truefor (i = 1 ; i <= n ; i ++ )
truetrueread(a[i]) ,
truetrues[i] = s[i-1]+a[i] ,
truetruemaxv = max(a[i] , maxv) ;
trueans = Bsearch() ;
trueprintf("%d %d\n", ans , dp(ans)) ;
true#ifdef  READ
truetruefclose(stdin) ; fclose(stdout) ;
true#else
truetruegetchar() ; getchar() ;
true#endif
truereturn 0 ;
}

热评文章