首页 > 其他 > 详细

【HDU-1051】Wooden Sticks 【线性DP】

时间:2020-04-07 13:49:05      阅读:72      评论:0      收藏:0      [点我收藏+]

  一堆n根木棍。每个棒的长度和重量是预先已知的。这些木棒将由木工机械一一加工。机器需要准备一些时间(称为准备时间)来准备处理木棍。设置时间与清洁操作以及更换机器中的工具和形状有关。木工机械
的准备时间如下: 

  (a)第一个木棍的准备时间为1分钟。

  (b)在处理长度为l和重量为w的棒之后,如果l <= l‘并且w <= w‘,则机器将不需要设置长度为l‘和重量w‘棒的设置时间。否则,将需要1分钟进行设置。您将找到处理给定的n根木棍的最短准备时间。

 

  3 
  5   
  4 9 5 2 2 1 3 5 1 4 
  3 
  2 2 1 1 2 2 
  3 
  1 3 2 2 3 1 
2
1
3

其实是很简单的一道线性dp,然鹅我手太笨半天调不过。

后一个木棍比前一个长且重,这不就是个不下降子序列??

那我们只要 l 进行排序, 求 w 的不下降子序列的最少划分数不就得了(反过来也彳亍)

根据dilworth定理(不知道的自己百度,我我也不会证),我们要做的就是求最长上升子序列。

数据不大, dp就可以氵过

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<iostream>
 5 const int maxn = 5005, inf = 0x3f3f3f3f;
 6 using namespace std;
 7 int f[maxn];
 8 struct node{
 9     int l, w;
10 }a[maxn];
11 bool cmp(node a, node b){
12     if(a.l == b.l) return a.w < b.w;
13     return a.l < b.l;
14 }
15 int main(){
16     int t; scanf("%d", &t);
17     while(t--){
18         int n; scanf("%d", &n);
19         for(int i=1; i<=n; i++) scanf("%d%d", &a[i].l, &a[i].w);
20         sort(a+1, a+1+n, cmp);
21         int maxx = 1;
22         for(int i=1; i<=n; i++){
23             f[i] = 1;
24             for(int j=1; j<i; j++){
25                 if(a[i].w<a[j].w && f[i]<f[j]+1){
26                     f[i] = f[j] + 1;
27                     maxx = max(maxx, f[i]);
28                 }
29             }
30         }
31         printf("%d\n", maxx);
32     }
33     return 0;
34 }

 

【HDU-1051】Wooden Sticks 【线性DP】

原文:https://www.cnblogs.com/hzoi-poozhai/p/12652554.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!