P2093 零件分组

题目描述

某工厂生产一批棍状零件，每个零件都有一定的长度（Li）和重量（Wi）。现在为了加工需要，要将它们分成若干组，使每一组的零件都能排成一个长度和重量都不下降（若i<j，则Li<=Lj，Wi<=Wj）的序列。请问至少要分成几组?

输入输出格式

输入格式：

第一行为一个整数N（N<=1000），表示零件的个数。第二行有N对正整数，每对正整数表示这些零件的长度和重量，长度和重量均不超过10000。

输出格式：

仅一行，即最少分成的组数。

输入输出样例

输入样例#1： 5 8 4 3 8 2 3 9 7 3 5 输出样例#1： 2

典型贪心问题，用快排，但我用的是冒泡，算得上是DP，最长不下降子序列。

#include <iostream> using namespace std; int a[1005],b[1005],la[1005]; int main() { int n,x,y; int i,j,t,s; cin>>n; for(i=1;i<=n;i++) cin>>a[i]>>b[i]; for(i=1;i<n;i++) for(j=i+1;j<=n;j++) if((a[i]==a[j]&&b[i]>b[j])||a[i]>a[j]) { t=a[i];a[i]=a[j];a[j]=t; t=b[i];b[i]=b[j];b[j]=t; } s=1; la[s]=b[1]; for(i=2;i<=n;i++) { x=0; y=-1; for(j=1;j<=s;j++) if(la[j]>x&&la[j]<=b[i]) { x=la[j]; y=j; } if(y==-1) { s++; la[s]=b[i]; } else la[y]=b[i]; } cout<<s; return 0; }