![BZOJ 1044: [HAOI2008]木棍分割(二分答案 + dp)](/default/index/img?u=aHR0cHM6Ly9iYnNtYXguaWthZmFuLmNvbS9zdGF0aWMvTDNCeWIzaDVMMmgwZEhBdmFXMWhaMlZ6TG1OdWFYUmliRzluTG1OdmJTOWliRzluTWpBeE5TODNNak00T1RZdk1qQXhOVEExTHpBeE1qQXhPREl3TkRRek56VTFNUzV3Ym1jPS5qcGc= "BZOJ 1044: [HAOI2008]木棍分割(二分答案 + dp)")
第一问可以二分答案,然后贪心来判断.
第二问dp, dp[i][j] = sigma(dp[k][j - 1]) (1 <= k <i, sum[i] - sum[k] <= ans) dp[i][j] 表示前i根木棍切了j次最大长度<=ans的方案数。sum[i]为1~i 的木棍长度和(前缀和).明显可以用滚动数组优化.然后又会发现, 对于每个dp[i][j]求和过程中,sum[i]不变,而sum[k]是单调递增,满足的k值是一连续的区间,且满足的最小k随i变大而变大,所以可以用一个变量累计.复杂度O(nm).
-------------------------------------------------------------------------------------------------
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#define rep(i, n) for(int i = 0; i < n; ++i)
#define Rep(i, l, r) for(int i = l; i <= n; ++i)
#define clr(x, c) memset(x, c, sizeof(x))
#define mod(x) ((x + 10007) %= 10007)
using namespace std;
const int maxn = 50000 + 5;
int n, m, ans = 0;
int sumL[maxn];
int d[maxn][2];
void Read() {
scanf("%d%d", &n, &m);
int t;
sumL[0] = 0;
Rep(i, 1, n) {
scanf("%d", &t);
sumL[i] = sumL[i - 1] + t;
}
}
bool jud(int ans) {
int cnt = m, front = 0, rear = 0;
while(rear < n) {
while(rear < n && sumL[rear + 1] - sumL[front] <= ans) rear++;
if(rear < n) {
front = rear;
if(--cnt < 0) return false;
}
}
return true;
}
void BS() {
int l = 0, r = sumL[n];
while(l <= r) {
int mid = (l + r) >> 1;
if(jud(mid)) { ans = mid; r = mid - 1; }
else l = mid + 1;
}
printf("%d ", ans);
}
void DP() {
int cur = 0, Ans = 0;
Rep(i, 1, n) d[i][cur] = sumL[i] <= ans ? 1 : 0;
d[0][0] = d[0][1] = 0;
while(m--) {
cur ^= 1;
int p = 0, sum = 0;
Rep(i, 1, n) {
while(sumL[i] - sumL[p] > ans) mod(sum -= d[p++][cur ^ 1]);
mod(d[i][cur] = sum);
mod(sum += d[i][cur ^ 1]);
}
mod(Ans += d[n][cur]);
}
printf("%d\n", Ans);
}
int main() {
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
Read();
BS();
DP();
return 0;
}
-------------------------------------------------------------------------------------------------
1044: [HAOI2008]木棍分割
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 2095 Solved: 761
[Submit][Status][Discuss]
Description
有n根木棍, 第i根木棍的长度为Li,n根木棍依次连结了一起, 总共有n-1个连接处. 现在允许你最多砍断m个连接处, 砍完后n根木棍被分成了很多段,要求满足总长度最大的一段长度最小, 并且输出有多少种砍的方法使得总长度最大的一段长度最小. 并将结果mod 10007。。。
Input
输入文件第一行有2个数n,m. 接下来n行每行一个正整数Li,表示第i根木棍的长度.
Output
输出有2个数, 第一个数是总长度最大的一段的长度最小值, 第二个数是有多少种砍的方法使得满足条件.
Sample Input
3 2
1
1
10
Sample Output
10 2
HINT
两种砍的方法: (1)(1)(10)和(1 1)(10)
数据范围
n<=50000, 0<=m<=min(n-1,1000).
1<=Li<=1000.
Source