【例题收藏】◇例题·IV◇ Wooden Sticks
◇例题·IV◇ Wooden Sticks
借鉴了一下 Candy? 大佬的思路 +传送门+ (=^-ω-^=)
来源:+POJ 1065+
◆ 题目大意
有n个木棍以及一台处理木棍的机器。第i个木棍用二元组 (li,wi) 表示,li 为它的长度,wi 为它的重量。
机器可以连续处理木棍{a[1],a[2]...a[m]}当且仅当对于每一个i(1≤i<m) la[i]<la[i+1] 且 wa[i]<wa[i+1] 。机器连续处理木棍的时间是1单位。你需要将这些木棍按一定顺序在机器中处理,求最少需要花费多少的时间。
例如:按顺序 ( 4 , 1 ) , ( 5 , 3 ) , ( 9 , 4 ) , ( 1 , 2 ) , ( 2 , 5 ) 处理,花费时间为2。
◆ 解析
这道题对STL的运用非常巧妙(我不知道为什么老师把这道题放在DP里……)
将问题简化一下,其实就是将木棍分成多个不上升序列,求最少序列数。我们不妨将这些序列设为 seq[1~m],那么判断一根木棍能否插入到某一个序列末尾,就是判断它的w和l是否都小于序列的末尾元素。
然后就是一个比较明显的贪心思想:若木棍x可以插入序列i或序列j的末尾,但是i的末尾要大于j的末尾,我们就把x插入i而不是j,这样能够让j插入更多的元素。
接下来就是实现了!
由于求不上升子序列和求不下降子序列是一个道理(?留给reader们思考一下),所以我们可以算最长不下降子序列。还有一个麻烦就是木棍是二元组,同时考虑两个值很麻烦,所以我们可以先sort一遍,按w为关键字(l为第二关键字),这样保证插入时w的这一维是不下降的。然后我们就只需要考虑 l 这一维。
由于我们只需要用到每一个不下降序列的末尾元素,我们可以定seq[i]表示第i个不下降序列的末尾元素。一开始所有序列seq都是空,而我们要使第一根木棍一定能够插入到序列中,我们就可以把序列末尾全部清空为负无穷。
然后就是STL的lower_bound()了——找到小于等于特定值的最大元素第一次出现的位置。插入 i 时,我们在序列末尾seq中查找小于等于 木棍i的l 的最大的序列末尾,然后插入该序列(贪心)。
◆ 源代码
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=,INF=int(1e9);
struct WOOD{
int w,l;
}wood[MAXN+];
int n;
int seq[MAXN+]; //seq[i]表示第i组连续处理的木棍最后处理的木棍的l
bool cmp(int a,int b){return a>b;}
bool cmp_(WOOD A,WOOD B) //按w为第一关键字排序,l为第二关键字
{
if(A.w>B.w) return ; //较小的放前面
if(A.w<B.w) return ;
return A.l<B.l;
}
int Solve()
{
int ans=;
sort(wood+,wood++n,cmp_); //先排序,排序后wood按w形成升序
fill(seq,seq+MAXN+,-INF); //初始化,这样第一根木棍无论如何都可以插入到seq中
for(int i=;i<=n;i++)
{
int pos=lower_bound(seq+,seq++n,wood[i].l,cmp)-seq; //找到最大的可以继续连续处理木棍的组数
seq[pos]=wood[i].l; //更新最后处理的l
ans=max(ans,pos); //处理答案
}
return ans;
}
int main()
{
int T;scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d%d",&wood[i].w,&wood[i].l);
printf("%d\n",Solve());
}
return ;
}
The End
Thanks for reading!
- Lucky_Glass
最新文章
- 用Kotlin实现Android定制视图(KAD 06)
- C++项目中的extern ";C"; {}
- 锋利的JQuery —— 事件和动画
- 脊柱外科病人资料管理系统的界面设计分析(2)--JOA评分记录的实现
- Java构建工具:如何用Maven,Gradle和Ant+Ivy进行依赖管理
- mysql中int转varchar
- path 环境变量
- 使用ICSharpCode.SharpZipLib.Zip实现压缩与解压缩
- 【图像配准】基于灰度的模板匹配算法(一):MAD、SAD、SSD、MSD、NCC、SSDA、SATD算法
- select的限制以及poll的使用
- Good Time 冲刺四
- python3之time、datetime、random
- Easyui-DataGrid 分页多选框 及 遍历所有选中项
- Dirichlet分布深入理解
- EZ 2018 02 26 NOIP2018 模拟赛(一)
- Redis内存淘汰机制
- 让IIS 7 如同IIS 8 第一次请求不变慢
- ctf百度杯十二月场what_the_fuck(一口盐汽水提供的答案)
- 【数论】【快速幂】CODEVS 2952 细胞分裂 2
- Android中打包JAR时获取资源ID的方法