BZOJ 1044 木棍分割 解题报告(二分+DP)
2018-06-17 23:43:04来源:未知 阅读 ()
来到机房刷了一道水(bian’tai)题。题目思想非常简单易懂(我的做法实际上参考了Evensgn 范学长,在此多谢范学长了)
题目摆上:
1044: [HAOI2008]木棍分割
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 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
1
1
10
Sample Output
HINT
两种砍的方法: (1)(1)(10)和(1 1)(10)
bool check(int x/*x表示我们二分的最长段的长度*/){ if(x < p)return false; int cut = 0,add = 0; for(int i = 1;i <= n;++i){ if(add + a[i] > x){ cut++;//cut表示当前已经分割了几次 if(cut > m)return false; add = 0; } add += a[i]; } return true; } while(l <= r){ mid = (l + r) >> 1; if(check(mid))r = mid - 1; else l = mid + 1; }
接下来求完了我们需要的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)辣!
终于完成了,接下来就是代码了:
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <cstdlib> 6 #include <algorithm> 7 using namespace std; 8 const int maxn = 50005; 9 const int maxm = 1005; 10 const int mod = 10007; 11 int get_num(){ 12 int num = 0; 13 char c; 14 bool flag = false; 15 while((c = getchar()) == ' ' || c == '\r' || c == '\n'); 16 if(c == '-') 17 flag = true; 18 else num = c - '0'; 19 while(isdigit(c = getchar())) 20 num = num * 10 + c - '0'; 21 return (flag ? -1 : 1)*num; 22 } 23 int n,m; 24 int a[maxn],ss[maxn]; 25 int f[maxn][2]; 26 int now,pre,len,p = 0,mid,ans = 0; 27 bool check(int x){ 28 if(x < p)return false; 29 int cut = 0,add = 0; 30 for(int i = 1;i <= n;++i){ 31 if(add + a[i] > x){ 32 cut++; 33 if(cut > m)return false; 34 add = 0; 35 } 36 add += a[i]; 37 } 38 return true; 39 } 40 int main(){ 41 memset(f,0,sizeof(f)); 42 memset(a,0,sizeof(a)); 43 memset(ss,0,sizeof(ss)); 44 n = get_num(); 45 m = get_num(); 46 for(int i = 1;i <= n;++i){ 47 a[i] = get_num(); 48 ss[i] = a[i] + ss[i-1]; 49 p = max(p,a[i]); 50 } 51 int l = 0,r = 50000000; 52 while(l <= r){ 53 mid = (l + r) >> 1; 54 if(check(mid))r = mid - 1; 55 else l = mid + 1; 56 } 57 len = r + 1; 58 now = 0; 59 pre = now^1; 60 int sumf = 0; 61 int mink = 0; 62 for(int i = 0;i <= m;++i){ 63 sumf = 0; 64 mink = 1; 65 for(int j = 1;j <= n;++j){ 66 if(i == 0) 67 if(ss[j] <= len)f[j][now] = 1; 68 else f[j][now] = 0; 69 else{ 70 while(mink < j && ss[j] - ss[mink] > len){ 71 sumf -= f[mink][pre]; 72 sumf = (sumf + mod) % mod; 73 mink++; 74 } 75 f[j][now] = sumf; 76 } 77 sumf += f[j][pre]; 78 sumf %= mod; 79 } 80 ans += f[n][now]; 81 ans %= mod; 82 now ^= 1; 83 pre = now ^ 1; 84 } 85 printf("%d %d\n",len,ans); 86 return 0; 87 }
附赠一张图片:
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- bzoj3569 DZY Loves Chinese II 2020-05-25
- bzoj4036 [HAOI2015]按位或 2020-04-26
- hdu1455 拼木棍(经典dfs) 2020-02-29
- 「BZOJ4173」数学 2020-01-15
- bzoj3944 Sum 2019-12-25
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash