首页 > 代码库 > 零件分组_DP
零件分组_DP
问题 C: 零件分组
时间限制: 1 Sec 内存限制: 64 MB提交: 31 解决: 14
[提交][状态][讨论版]
题目描述
某工厂生产一批棍状零件，每个零件都有一定的长度（Li）和重量（Wi）。现在为了加工需要，要将它们分成若干组，使每一组的零件都能排成一个长度和重量都不下降（若 i<j，则 Li<=Lj，Wi<=Wj）的序列。请问至少要分成几组?
输入
第一行为一个整数 N（N<=1000），表示零件的个数。第二行有 N 对正整数，每对正整数表示这些零件的长度和重量，长度和重量均不超过 10000。
输出
仅一行，即最少分成的组数。
样例输入
58 4 3 8 2 3 9 7 3 5样例输出
2解题思路：动态规划求最大递减子序列（最少分组数=最大反链数_dilworth定理）#include <iostream>#include <cstdio>#include <algorithm>using namespace std;struct node{ int l; int w;};node a[1005];int cmp(node a,node b){ return a.l<b.l||a.l==b.l&&a.w<b.w;}int main(){ int n; int sum[1005]; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d %d",&a[i].l,&a[i].w); sum[i]=0; } sort(a,a+n,cmp); int ans=0; for(int i=0;i<n;i++){ int maxx=0; for(int j=0;j<i;j++){ if(a[j].w>a[i].w){ maxx=max(maxx,sum[j]); } } sum[i]=maxx+1; ans=max(ans,sum[i]); } printf("%d",ans); return 0;}
零件分组_DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。