BZOJ1044: [HAOI2008]木棍分割 (二分 + DP)
发布日期:2022-03-15 04:11:15 浏览次数:40 分类:技术文章

本文共 1980 字,大约阅读时间需要 6 分钟。

题意:n根木棍依次连在一起 最多切m个端点 使得最长的一段最小

   在保证最长的最小的情况下 有多少种不同的切法

题解:第一问傻子都知道二分

   第二问想了一会不会做 但其实就是很简单的dp

   dp[i][j]表示切完第i刀切到第j段后面的的种数

   想了一下觉得空间过不去 然而这个是可以滚动的 因为每一刀的转移都只和前一刀有关系 再优化下时间

   预处理一下last[i]表示在第i个木棍后面切的话 至少要在last[i]这个点及以后也切一下

   跃然纸上的转移 dp[i][j] += dp[i - 1][k]  if(last[j] <= k < j) 但这是个接近n^3的复杂度

   然后发现每次转移 dp[i][j]都是加的相同一段 所以我们可以每次前缀和搞一下

 

#include 
using namespace std;const int mod = 10007;int n, m;int q[50005];int sum[50005];int last[50005];int dp[2][50005];int pre[2][50005];int ans1, ans2;int check(int x){ int res = 0; int cnt = 0; for(int i = 1; i <= n; i++) { res += q[i]; if(res > x) cnt++, res = q[i]; } return cnt;}int main(){ ans2 = 0; scanf("%d%d", &n, &m); int l = 0, r = 0; for(int i = 1; i <= n; i++) { scanf("%d", &q[i]); l = max(l, q[i]); r += q[i]; } int mid = l + r >> 1; while(l + 1 < r) { mid = l + r >> 1; if(check(mid) <= m) ans1 = mid, r = mid; else l = mid; } if(check(l) <= m) ans1 = l; int zsum = 0; int p = 1; for(int i = 1; i <= n; i++) { zsum += q[i]; while(zsum > ans1) zsum -= q[p], p++; last[i] = p - 1; if(last[i] == 0) dp[1][i] = 1; } ans2 += dp[1][n]; for(int i = 1; i <= n; i++) pre[1][i] = (dp[1][i] + pre[1][i - 1]) % mod; for(int i = 2; i <= m + 1; i++) { memset(dp[i & 1], 0, sizeof(dp[i & 1])); pre[i & 1][i - 1] = 0; for(int j = i; j <= n; j++) { dp[i & 1][j] = (dp[i & 1][j] + pre[(i - 1) & 1][j - 1]) % mod; if(last[j]) dp[i & 1][j] = (dp[i & 1][j] - pre[(i - 1) & 1][last[j] - 1]) % mod; dp[i & 1][j] = (dp[i & 1][j] + mod) % mod; } for(int j = i; j <= n; j++) pre[i & 1][j] = (pre[i & 1][j - 1] + dp[i & 1][j]) % mod; ans2 = (ans2 + dp[i & 1][n]) % mod; } printf("%d %d\n", ans1, ans2); return 0;}
View Code

 

   

   

转载于:https://www.cnblogs.com/lwqq3/p/9774514.html

转载地址:https://blog.csdn.net/weixin_30536513/article/details/99769993 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:SQL:waitfor的使用
下一篇:Android深度探索读书笔记 第六章

发表评论

最新留言

第一次来,支持一个
[***.219.124.196]2024年03月24日 02时15分36秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

华为手机的分类有何区别_动画有哪些分类?又有何区别? 2019-04-21
编程迷宫_跟我学编程第十期——迷宫游戏 2019-04-21
一键生成安卓证书_【带壳截图+电影台词 生成器】 2019-04-21
北斗轨迹记录_北斗定位+智慧4G视频校车行业解决方案 2019-04-21
存放哪些内容 项目中vuex_房屋安全鉴定中房屋抗震检测内容有哪些 2019-04-21
extjs的panel怎么自适应高度_Ext Js自适应高度 2019-04-21
ilm 和dlm差异_Oracle 的信息生命周期管理工具(ILM assistant) 2019-04-21
斥候密报_斥候密报《最强王者》三国幕后巾帼之黄月英_吉吉建站手游网 2019-04-21
python的循环控制结构是什么_7.Python控制和循环结构 2019-04-21
python 死循环插曲变量_FishC03 讲:python小插曲之变量和字符串 2019-04-21
车型代号对照表_车型代号对照表_相关文章专题_写写帮文库 2019-04-21
arcgis符号方向_ArcGIS制图表达-河流渐变与符号旋转 2019-04-21
springboot 实现机器学习_SpringBoot架构浅谈 2019-04-21
oss批量上传工具_OssExplorer一OSS的专用客户端工具【最新版】_Windows_Windows server 2008-云市场-阿里云... 2019-04-21
login控件authenticate_ASP:Login控件(登录控件) 2019-04-21
drf 安装_drf 安装与配置 2019-04-21
c++ loadlibrary 初始化对象_C++构造函数和初始化表 2019-04-21
jmeter mysql driver_jmeter测试mysql数据库之JDBC请求 2019-04-21
mysql group by cube_SQL Server 之 GROUP BY、GROUPING SETS、ROLLUP、CUBE 2019-04-21
mysql mgr 5.6_mysql MGR高可用配置 2019-04-21