【POJ1065】Wooden Sticks Dilworth定理（偏序集定理2）-程序员宅基地

题意：

可以视为跟POJ1548相同，就是n个点（二维），要求分堆，每堆中点要求单调递增（A的x和y值都比B小则A<B），问最少分几堆。

题解：参见我的另一篇博客

然后贴代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 6000
#define inf 0x3f3f3f3f
using namespace std;
struct KSD
{
	int x,y;
	bool operator < (const KSD &a)const
	{if(x==a.x)return y<a.y;return x<a.x;}
}s[N];
int n,f[N];
int main()
{
//	freopen("test.in","r",stdin);
	int i,j,g;
	s[0].y=inf;
	scanf("%d",&g);
	while(g--)
	{
		scanf("%d",&n);
		for(i=1;i<=n;i++)scanf("%d%d",&s[i].x,&s[i].y);
		sort(s+1,s+n+1);
		for(i=1;i<=n;i++)
		{
			f[i]=0;
			for(j=i-1;j>=0;j--)
			{
				if(s[j].y>s[i].y)f[i]=max(f[i],f[j]+1);
			}
		}
		int ans=0;
		for(i=1;i<=n;i++)ans=max(ans,f[i]);
		printf("%d\n",ans);
	}
	return 0;
}

本文链接：https://blog.csdn.net/Vmurder/article/details/40818831

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

领导让小明找几家OA供应商，小明发过去，结果被骂工作不用心。-程序员宅基地

文章浏览阅读469次，点赞13次，收藏7次。OA是公司最常用的管理系统之一，难度系数也不高，国内成熟的产品非常多，面对琳琅满目的产品该如何选择呢？本文为您解密。

安装ESIM事件相机模拟器遇到的一些问题及解决方法_failed << catkin_tools_prebuild:cmake [ exited wit-程序员宅基地

文章浏览阅读2.8k次。如果您的系统上尚未安装，请安装ROS。一行代码安装ROS的方法另一篇博文已经写过了点击此处我装的版本是ros的noetic，对应ubuntu20.04我们建议专门为模拟器创建一个新的 catkin 工作空间，如下所示：mkdir -p ~/sim_ws/src && cd ~/sim_wscatkin initcatkin config --extend /opt/ros/kinetic --cmake-args -DCMAKE_BUILD_TYPE=Releasevcsto_failed << catkin_tools_prebuild:cmake [ exited with code 1 ]

Java——十进制转换为任意进制（两种方法）_java 实现十进制转换为任意进制-程序员宅基地

文章浏览阅读1.9w次，点赞15次，收藏60次。1. 方法一 package com.zth;import java.util.Scanner;public class JinZhi { // 十进制转换为 n 进制 public String fun(int n,int num) { // n 表示目标进制, num 要转换的值 String str= ""; int yushu ; // ..._java 实现十进制转换为任意进制

C#学生选课及成绩管理系统-程序员宅基地

文章浏览阅读22次。（C#开发）C#学籍管理系统（完整数据库及运行源代码）（有完整设计报告）有需要随时联系我，我基本都在，能秒回！效果如下图所示！！#c语言 #选课成绩管理系统

2、使用STM32CubeMX新建工程点亮LED_1、用cubemx新建工程,点亮开发板node-a 上的led灯。(基于国信开发板实现)-程序员宅基地

文章浏览阅读654次。前言在配置好CubeMX之后，就是新建工程的开始了，本博客我们会很详细的介绍STM32CubeMx的基本使用和如何创建一个新的工程并且点亮LED灯面向初学者。前期准备：1、STM32硬件（我的是STM32F407ZE和STM32F103ZE）2、STM32CubeMx软件、 IDE Keil（MDK-ARM）软件3、STM32F4xxHAL库新建工程1在主界..._1、用cubemx新建工程,点亮开发板node-a 上的led灯。(基于国信开发板实现)

C#简单操作Lotus Notes邮件_notes邮箱怎么调出developer编程-程序员宅基地

文章浏览阅读4.6k次。前段时间简单的研究了一下.NET操作Lotus Notes邮件的实现，具体的操作包括邮件的读取和发送，而且都要包含附件，其间参考了《在 Microsoft .NET 应用程序中使用 IBM Lotus Domino》一文，现在把成果和大家分享一下。本文将分为获取用户列表、发送邮件、收取邮件三个部分，并会在文末提供范例程序（Visual Studio 2008）的下载。引用如果_notes邮箱怎么调出developer编程

随便推点

小程序使用AntV f2写双Y轴折线图及遇到的问题_f2-canvas y轴-程序员宅基地

文章浏览阅读2.8k次。1.根据官方文档仅有的部分内容，可知，不管是折线图，柱状图还是饼图，数据都要使用它规定的数据格式才可以。下面开始写我所用到的图表1.双Y轴双折线图的写法效果：//注意部分：数据带有双引号，Y轴上不会从小到大排列const app = getApp()let chart = null;function initChart(canvas, width, height,) { // 使用 F2 绘制图表 const data =[{time:'07:00:00--07:59:69', kdj:2_f2-canvas y轴