bzoj 2044 三维导弹拦截 —— 最小路径覆盖
2024-09-22 03:54:45
题目: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 ;
}
最新文章
- linux基础命令之:vi模式下查找和替换
- DNA Pairing
- 常见的Robotium测试的问题总结:
- Linux &; Python 导航目录
- Android中监听webview监听是否加载完成
- Android常用布局、文件存储与权限、XML
- springboot+CXF开发webservice对外提供接口(转)
- Android不同系统版本依然能调用到正确的API方法Demo——Service调用startForeground举例
- JFree图表
- go语言打造个人博客系统(二)
- js 取一定范围内的整数
- 【commons】时间日期工具类——commons-lang3-time
- 过滤器(Filter)与拦截器(Interceptor)区别
- wget 下载命令
- Hive的UDF是什么?
- Zabbix 创建触发器
- LeetCode(13):罗马数字转整数
- .net 系列:Expression表达式树、lambda、匿名委托 的使用【转】
- 在U盘上安装Windows 7的详细步骤
- Java API 各个包的内容解释
热门文章
- oracle 清理跟踪文件.trc .trm
- flask——CSRFToken保护
- Mozilla新特性只支持https网站
- type=";application/javascript";
- 【Codeforces 988D】Points and Powers of Two
- Leetcode 92.反转链表
- linux安装java mysql tomcat 环境
- [bzoj1572][Usaco2009 Open]工作安排Job_贪心_堆
- HUD——1286 找新朋友
- NetCore实现全局异常捕捉统一处理