来到机房刷了一道水(bian’tai)题。题目思想非常简单易懂(我的做法实际上参考了Evensgn 范学长,在此多谢范学长了)

题目摆上:

1044: [HAOI2008]木棍分割

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 3162  Solved: 1182
[Submit][Status][Discuss]

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)

多谢范学长的博客教会了我这道DP的优化。
接下来说说这道题的思路:
首先我们需要求被分割后的最长的木条的长度,这个很简单,二分+贪心check即可,跟基本的套路一样,相信大家都能理解:
bool check(int x/*x表示我们二分的最长段的长度*/){
if(x < p)return false;
int cut = ,add = ;
for(int i = ;i <= n;++i){
if(add + a[i] > x){
cut++;//cut表示当前已经分割了几次
if(cut > m)return false;
add = ;
}
add += a[i];
}
return true;
} while(l <= r){
mid = (l + r) >> ;
if(check(mid))r = mid - ;
else l = mid + ;
}

接下来求完了我们需要的len,就应该求有多少种方案可以满足len了。

众所周知,动态规划的第一步是要写出状态……然后再来搞

我们设f[i][j]表示前i段一共分割了j次,设ss[i]为a[i]的前缀和,然后写出dp方程:

f[i][j] = Σf[k][j-1] 其中k要满足的条件是(1 <= k < i) && (ss[i] - ss[k] <= len)(这是很容易从题目中得出的)。

于是我们就可以完成了。

但是这样也太简单了吧……毕竟是HAOI的题目,如果这么简单就是NOIP难度了(虽然本人不否认以前的省选题目也有NOIP难度的)

然后注意到数据范围:n<=50000,0<=m<=min(n-1,1000)

我们注意到我们程序的时间复杂度实际上是O(n^2 m) 的,这明显就是爆了时间的。

那然后该怎么办呢?

我们可以注意到,如果我们设sumf 表示枚举到k的时候Σf[k][j-1],(1 <= k < i) && (ss[i] - ss[k] <= len),mink表示满足(1 <= k < i) && (ss[i] - ss[k] <= len)的最小的k。

其实对于 f[i][Now] ,其实是 f[mink][Last]...f[i-1][Last] 这一段 f[k][Last] 的和,mink 是满足 Sum[i] - Sum[k] <= Len 的最小的 k ,对于从 1 到 n 枚举的 i ,相对应的 mink 也一定是非递减的(因为 Sum[i] 是递增的)。我们记录下 f[1][Last]...f[i-1][Last] 的和 Sumf ,mink 初始设为 1,每次对于 i 将 mink 向后推移,推移的同时将被舍弃的 p 对应的 f[p][Last] 从 Sumf 中减去。那么 f[i][Now] 就是 Sumf 的值。(此段复制自Evensgn的博客,因为我觉得自己可能写不出来这么详细)

这样我们就不必枚举k,时间复杂度就降低到可以接受的O(nm)了。

但是这样就完成了?别天真了,还有一个坑那,时间解决了,空间呢?我们的空间复杂度是O(nm)啊,用计算器算一下明显超了。

这时候的DP有一个技巧(类似于飞扬的小鸟NOIP2014),我们发现其实j所属的那一维,只能由j-1转移而来,所以可以使用最常用的手段——滚动数组,来滚动掉第二维

使用now和pre,f[maxn][2],now和pre只能为0或1,且pre = now^1,每完成一遍外层m循环更新now ^= 1,pre = now^1。

这样子我们的空间复杂度也降到可以接受的O(n)辣!

终于完成了,接下来就是代码了:

 #include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int maxn = ;
const int maxm = ;
const int mod = ;
int get_num(){
int num = ;
char c;
bool flag = false;
while((c = getchar()) == ' ' || c == '\r' || c == '\n');
if(c == '-')
flag = true;
else num = c - '';
while(isdigit(c = getchar()))
num = num * + c - '';
return (flag ? - : )*num;
}
int n,m;
int a[maxn],ss[maxn];
int f[maxn][];
int now,pre,len,p = ,mid,ans = ;
bool check(int x){
if(x < p)return false;
int cut = ,add = ;
for(int i = ;i <= n;++i){
if(add + a[i] > x){
cut++;
if(cut > m)return false;
add = ;
}
add += a[i];
}
return true;
}
int main(){
memset(f,,sizeof(f));
memset(a,,sizeof(a));
memset(ss,,sizeof(ss));
n = get_num();
m = get_num();
for(int i = ;i <= n;++i){
a[i] = get_num();
ss[i] = a[i] + ss[i-];
p = max(p,a[i]);
}
int l = ,r = ;
while(l <= r){
mid = (l + r) >> ;
if(check(mid))r = mid - ;
else l = mid + ;
}
len = r + ;
now = ;
pre = now^;
int sumf = ;
int mink = ;
for(int i = ;i <= m;++i){
sumf = ;
mink = ;
for(int j = ;j <= n;++j){
if(i == )
if(ss[j] <= len)f[j][now] = ;
else f[j][now] = ;
else{
while(mink < j && ss[j] - ss[mink] > len){
sumf -= f[mink][pre];
sumf = (sumf + mod) % mod;
mink++;
}
f[j][now] = sumf;
}
sumf += f[j][pre];
sumf %= mod;
}
ans += f[n][now];
ans %= mod;
now ^= ;
pre = now ^ ;
}
printf("%d %d\n",len,ans);
return ;
}

附赠一张图片:

BZOJ 1044 木棍分割 解题报告(二分+DP)-LMLPHP

04-21 06:09
查看更多