Toggle navigation
NKZX_NOI_OJ
常见问答
题库
来源/分类
状态
排名
竞赛&作业
Login
问题1227--零件分组
1227: 零件分组
时间限制:
1 Sec
内存限制:
64 MB
提交:
0
解决:
0
[
提交
] [
状态
] [
讨论版
] [命题人:
]
题目描述
某工厂生产一批棍状零件,每个零件都有一定的长度(L
i
)和重量(W
i
)。现在为了加工需要,要将它们分成若干组,使每一组的零件都能排成一个长度和重量都不下降(若 i<j,则 L
i
<=L
j
,W
i
<=W
j
)的序列。请问至少要分成几组?
输入
第一行为一个整数 N(N≤1000),表示零件的个数。第二行有 N 对正整数,每对正整数表示这些零件的长度和重量,长度和重量均不超过 10000,每两个数之间用一个空格隔开。
输出
一行一个整数,即最少分成的组数。
样例输入
Copy
5 8 4 3 8 2 3 9 7 3 5
样例输出
Copy
2
来源/分类
动态规划算法