题目:https://www.lydsy.com/JudgeOnline/problem.php?id=2044

第一问暴力 n^2 即可;

注意这道题对位置没要求!所以先按第一维排序一下即可;

然后拆入点和出点,求一个最小路径覆盖即可。

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int const maxn=;
int n,f[maxn],ans,mx,hd[maxn],ct,to[maxn*maxn],nxt[maxn*maxn],pre[maxn];
bool vis[maxn];
struct N{int x,y,z;}p[maxn];
void add(int x,int y){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct;}
bool cmp(N a,N b){return a.x<b.x;}
bool dfs(int x)
{
for(int i=hd[x],u;i;i=nxt[i])
{
if(vis[u=to[i]])continue;
vis[u]=;
if(!pre[u]||dfs(pre[u])){pre[u]=x; return ;}
}
return ;
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z);
sort(p+,p+n+,cmp);
for(int i=;i<=n;i++)
{
f[i]=;
for(int j=;j<i;j++)
if(p[j].x<p[i].x&&p[j].y<p[i].y&&p[j].z<p[i].z)//p[i].x!=p[j].x!
{
f[i]=max(f[i],f[j]+);
add(j,i);//j -> i
}
mx=max(mx,f[i]);
}
for(int i=;i<=n;i++)
{
memset(vis,,sizeof vis);
if(dfs(i))ans++;
}
ans=n-ans;
printf("%d\n%d\n",mx,ans);
return ;
}

最新文章

  1. linux基础命令之:vi模式下查找和替换
  2. DNA Pairing
  3. 常见的Robotium测试的问题总结:
  4. Linux &amp; Python 导航目录
  5. Android中监听webview监听是否加载完成
  6. Android常用布局、文件存储与权限、XML
  7. springboot+CXF开发webservice对外提供接口(转)
  8. Android不同系统版本依然能调用到正确的API方法Demo——Service调用startForeground举例
  9. JFree图表
  10. go语言打造个人博客系统(二)
  11. js 取一定范围内的整数
  12. 【commons】时间日期工具类——commons-lang3-time
  13. 过滤器(Filter)与拦截器(Interceptor)区别
  14. wget 下载命令
  15. Hive的UDF是什么?
  16. Zabbix 创建触发器
  17. LeetCode(13):罗马数字转整数
  18. .net 系列:Expression表达式树、lambda、匿名委托 的使用【转】
  19. 在U盘上安装Windows 7的详细步骤
  20. Java API 各个包的内容解释

热门文章

  1. oracle 清理跟踪文件.trc .trm
  2. flask——CSRFToken保护
  3. Mozilla新特性只支持https网站
  4. type=&quot;application/javascript&quot;
  5. 【Codeforces 988D】Points and Powers of Two
  6. Leetcode 92.反转链表
  7. linux安装java mysql tomcat 环境
  8. [bzoj1572][Usaco2009 Open]工作安排Job_贪心_堆
  9. HUD——1286 找新朋友
  10. NetCore实现全局异常捕捉统一处理