杭电OJ 1051:Wooden Sticks

本文主要是介绍杭电OJ 1051:Wooden Sticks，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这个题目的大意是有一个处理木材的机器，处理第一根木材的时候需要调整，后面的木材如果长度不小于前面的木材并且重量也不小于前面的木材则机器不需要重新调整，否则就需要调整，调整一次花费的时间为1，问机器最少要调整几次？

这个问题其实可以转换为求最长递减子序列。转化过程：先对多所有的木材按长度从小到大排序，然后按重量求最长递减子序列，子序列元素的个数就是机器要调整的次数，因为这个序列中的元素是不可能排在其他的元素的后面的。求最长递减子序列有nlogn的算法，但是这个题目数据量不是很大，n*n的算法也可以通过。

C++代码：

#include<stdio.h>
#include<algorithm>
using namespace std;
const int N=5010;
struct stick{int l,w;
}arr[N];
bool cmp(stick a,stick b){if(a.l==b.l)return a.w<b.w;return a.l<b.l;
}
int main(){int T,n;int dp[N];//freopen("1.txt","r",stdin);scanf("%d",&T);while(T--){scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d%d",&arr[i].l,&arr[i].w);}sort(arr,arr+n,cmp);dp[0]=1;for(int i=1;i<n;i++){int index=-1,max=

这篇关于杭电OJ 1051:Wooden Sticks的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---