ZOJ1025-Wooden Sticks 加工木棒问题
【问题描述】
现有n根木棒，已知它们的长度和重量。要用一部木工机一根一根地加工这些木棒。该机器在加工过程中需要一定的准备时间用于清洗机器、调整工具和模板。
木工机需要的准备时间如下：
（1） 第一根木棒需要1min的准备时间；
（2） 在加工了一根长为l，重为w的木棒后，接着加工一根长为l’(l≤l’)，
重为w’(w≤w’)的木棒是不需要任何准备时间的，否则需要1min的准备时间。
给定n根木棒，你要找到最少的准备时间。例如现在有长度和重量分别为（4,9）、（5,2）、（2,1）、（3,5）和（1,4）的5根木棒，那么所需准备时间最少为2min，顺序为（1,4）-》（3,5）-》（4,9）-》（2,1）-》（5,2）。
【输入】
输入有多组测试例。输入数据的第一行是测试例的个数T。
每个测试例两行：
第一行是一个整数n（1≤n≤5000），表示有多少根木棒；
第二行包括n×2个整数，表示l1,w1,l2,w2,l3,w3,…,ln,wn，全部不大于10000，其中li和wi表示第i根木棒的长度和重量。
数据由一个或多个空格分隔。
【输出】
输出是以分钟为单位的最少准备时间，一行对应一个测试例。
【输入样例】
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
思路：
拿分析的样例来看，直接想到了离散上的偏序集，但只是想到了，不知道该怎么解。。。
看了下题解有了思路。先通过一轮cmp构造的排序，将问题进行转化——按照每个棒子的长度从小到大进行排序，然后得到基于棒子长度从小到大排序的棒子重量数组，将这个数组提取到w中保存，或者你不提出来也行，我就是为了方便，我称之为空间换简洁。
然后我们在把2维的偏序关系降到1维后（对，这个题就是降维打击：），就发现现在问题已经转换成了求w数组的最长上升子序列的最小个数，而这个问题，可以再次转换成求w数组的最长递减子序列的长度。后者的转换很容易理解，比如这个数组w的最长递减子序列的长度为5，那这5个值肯定各自在一个独立的最长上升子序列中。
两行大概就把问题的核心说清了，然后coding
#include <iostream>#include <cstring>#include <algorithm>#define N 5007using namespace std;int n,T;struct stick{ int l,w;} sticks[N];int w[N];int dp[N];bool cmp(stick a,stick b){ if(a.l == b.l) return a.w < b.w; else if(a.l < b.l) return true; return false;}int LIS(int* w){ int j;//j为当前最大结束点的坐标 dp[j=1] = w[1]; for(int i = 2;i <= n;i++) { if(w[i] < dp[j]) dp[++j] = w[i]; else if(w[i] == dp[j]) continue; else { for(int k = j;k >= 1;k--) { if(k == 1) dp[1] = w[i]>dp[1]?w[i]:dp[1]; //找到所有“合适”的位置 if(w[i]>dp[k] && w[i]<dp[k-1]) dp[k] = w[i]; } } } return j;}int main(){ cin>>T; while(T--) { cin>>n; int ans = 0; for(int i = 1;i <= n;i++) cin>>sticks[i].l>>sticks[i].w; sort(sticks+1,sticks+1+n,cmp); for(int i = 1;i <= n;i++) w[i] = sticks[i].w; cout<<LIS(w)<<endl; } return 0;}
联系客服
