这道题，首先想到的就两个，一是贪心，二是动规，然而 1<=N<=100000;1<=w_i<=10000 的数据范围实在不敢恭维，所以说第一想法是错的。仔细一想，首先，我们需要的是前一层的宽度大于等于下一层，高度(厚度)都是1，而宽度就是连续几个稻草块的宽度和,所以我们想到的方法就是 分段 使每一段稻草块的宽度和递减，并且使段数最多，而要使段数最多，则第一段就要越少（设总宽度 W ， Wi>=Wj ,因此最少 W/W1 段），最后得出的段数就是高度了，那么这道题应该就化解了。
(转载请注明出处：http://www.cnblogs.com/Kalenda/)
P1233: [Usaco2009Open]干草堆tower的更多相关文章
-
【BZOJ 1233】 [Usaco2009Open]干草堆tower （单调队列优化DP）
1233: [Usaco2009Open]干草堆tower Description 奶牛们讨厌黑暗. 为了调整牛棚顶的电灯的亮度,Bessie必须建一座干草堆使得她能够爬上去够到灯泡 .一共有N大包的 ...
-
bzoj1233[Usaco2009Open]干草堆tower 单调队列优化dp
1233: [Usaco2009Open]干草堆tower Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 983 Solved: 464[Submi ...
-
bzoj 1233: [Usaco2009Open]干草堆tower
1233: [Usaco2009Open]干草堆tower Description 奶牛们讨厌黑暗. 为了调整牛棚顶的电灯的亮度,Bessie必须建一座干草堆使得她能够爬上去够到灯泡 .一共有N大包的 ...
-
bzoj1233: [Usaco2009Open]干草堆tower
Description 奶牛们讨厌黑暗. 为了调整牛棚顶的电灯的亮度,Bessie必须建一座干草堆使得她能够爬上去够到灯泡 .一共有N大包的干草(1<=N<=100000)(从1到N编号) ...
-
BZOJ1233 [Usaco2009Open]干草堆tower 【单调队列优化dp】
题目链接 BZOJ1233 题解 有一个贪心策略:同样的干草集合,底长小的一定不比底长大的矮 设\(f[i]\)表示\(i...N\)形成的干草堆的最小底长,同时用\(g[i]\)记录此时的高度 那么 ...
-
bzoj1233 [Usaco2009Open]干草堆tower 【单调队列dp】
传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1233 单调队列优化的第一题,搞了好久啊,跟一开始入手斜率优化时感觉差不多... 这一题想通了 ...
-
BZOJ1233 [Usaco2009Open]干草堆tower 和 BZOJ3549 [ONTAK2010]Tower
题意 Problem 3549. -- [ONTAK2010]Tower 3549: [ONTAK2010]Tower Time Limit: 10 Sec Memory Limit: 64 MBS ...
-
bzoj 1233: [Usaco2009Open]干草堆tower 【想法题】
首先这题的$n^3$的DP是比较好想的 $f[i][j]$表示用前$i$包干草 且最顶层为第$j+1$包到第$i$包 所能达到的最大高度 然而数据范围还是太大了 因此我们需要去想一想有没有什么单调性 ...
-
BZOJ1233 [Usaco2009Open]干草堆tower[贪心+单调队列优化]
地址 注意思路!多看几遍! 很巧妙的一道题.不再是决策点以dp值中一部分含j项为维护对象,而是通过维护条件来获取决策. 首先有个贪心策略,让底层的宽度尽可能小,才能让高度尽可能高.所以应该倒着dp,表 ...
随机推荐
-
3-linux下部署tomcat应用
linux下部署tomcat应用 相关软件下载 jdk http://www.oracle.com/technetwork/java/javase/downloads/jdk8-downlo ...
-
Android View 简析
基于android 4.4上源码分析: setContentView流程: getwindow() ->setContentView() -> installDecor() -> a ...
-
不经过 App store 的安装方式（转）
所有安装到真机(非越狱)的应用(可以是 .app ,也可以是 .ipa ,只要编译时选的是编译成 Arm 的就好..app 转 .ipa 只需要一条命令) 都必须经过证书签名.证书主要有三大种: 企业 ...
-
第七章 springboot + retrofit(转载)
本篇博客转发自:http://www.cnblogs.com/java-zhao/p/5350861.html retrofit:一套RESTful架构的Android(Java)客户端实现. 好处: ...
-
IE条件注释详解
IE条件注释是微软从IE5开始就提供的一种非标准逻辑语句,作用是可以灵活的为不同IE版本浏览器导入不同html元素,如:样式表,html标签等.很显然这种方法的最大好处就在于属于微软官方给出的兼容解决 ...
-
转载: ABAP动态内表操作
顾名思义,动态表的列是可以根据数据的变化而变化的,会使报表显示更简洁漂亮. 以下是实现方法. ------------------------------------------- 1, 创建动态内表 ...
-
[转贴]从零开始学C++之STL（二）：实现一个简单容器模板类Vec（模仿VC6.0 中 vector 的实现、vector 的容量capacity 增长问题）
首先,vector 在VC 2008 中的实现比较复杂,虽然vector 的声明跟VC6.0 是一致的,如下: C++ Code 1 2 template < class _Ty, cl ...
-
Python爬虫实战（2）：爬取京东商品列表
1,引言 在上一篇<Python爬虫实战:爬取Drupal论坛帖子列表>,爬取了一个用Drupal做的论坛,是静态页面,抓取比较容易,即使直接解析html源文件都可以抓取到需要的内容.相反 ...
-
Routeros 计划任务连线/断线ADSL
老板吩咐,要求晚上11点前断网,目的是让大家伙早睡早起. 不想使用Panabit来做策略,阿童木的D2500C还是性能不足,就用ROS的计划任务. 第1步 校时 时间要准,要不控制个乱七八糟. 操作路 ...
-
SpringMVC 支持使用Servlet原生API作为目标方法的参数
具体支持一下类型: * HttpServletRequest * HttpServletResponse * HttpSession * java.security.Pricipal * Locale ...