题目描述
某工厂生产一批棍状零件,每个零件都有一定的长度(Li)和重量(Wi)。现在为了加工需要,要将它们分成若干组,使每一组的零件都能排成一个长度和重量都不下降。
(输入第一行为一个整数N(N<=1000),表示零件的个数。
第二行有N对正整数,每对正整数表示这些零件的长度和重量,长度和重量均不超过10000。
输出仅一行,即最少分成的组数。)
输入
5
8 4 3 8 2 3 9 7 3 5
输出
2
思路
贪心
先按照长度进行递增排序,如果长度相同再按质量递增排序
从前往后遍历,如果后面的某个零件质量比当前选择的零件小且未分组,则分为同一组,并标记已分组
C++ 代码1
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 10001, INF = 0x3f3f3f3f;
int n;
//int l[N],w[N];
struct node {
int l, w;
} s[N];
bool cmp(node a, node b) { //以长度为主键递增排序
if (a.l == b.l) return a.w < b.w;
return a.l < b.l;
}
bool p[N];//标记数字是否已分组过
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> s[i].l >> s[i].w;
}
sort(s + 1, s + 1 + n, cmp); //递增排序
// for (int i = 1; i <= n; i++) {
// cout << s[i].l << " " << s[i].w << endl;
// }
int cnt = 0;//标记组数
for (int i = 1; i <= n - 1; i++) {
if (!p[i]) {
int t = i; //记录当前位置
p[i] = 1;
cnt++;//组数加一
for (int j = i + 1; j <= n; j++) {
if (s[t].w <= s[j].w && s[t].l <= s[j].l && !p[j]) { //是呈下降序列且未分组过
p[j] = 1;//标记已分组
t = j;//记录结束位置
}
}
}
}
cout << cnt;
return 0;
}
思路2
DP
当要求最长上升子序列的问题时,即求LIS
当题目要求求最长上升子序列的最少个数时,即可以转换为最长下降子序列的长度(详细可见Acwing1010 拦截导弹
)
反之也是成立的**
C++ 代码1
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cctype>
#include<string>
using namespace std;
typedef struct {
int l;
int w;
}LA;
LA a[1010];
int dp[1010];
int cmp(LA a,LA b)
{
if(a.l!=b.l) return a.l<b.l;//cmp的定义
else return a.w<b.w;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
int i,j;
for(i=0;i<n;i++){
scanf("%d%d",&a[i].l,&a[i].w);
dp[i]=1;
}
sort(a,a+n,cmp);
//int ma;
int ans=0;
for(i=1;i<n;i++)
{
for(j=0;j<i;j++)
{
if(a[i].w<a[j].w)
{
dp[i]=max(dp[j]+1,dp[i]);
}
}
ans=max(dp[i],ans);
}
printf("%d\n",ans);
}
return 0;
}