比赛 |
20120615 |
评测结果 |
AAAAAAAAAA |
题目名称 |
导弹拦截 |
最终得分 |
100 |
用户昵称 |
kaaala |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2012-06-15 16:28:16 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int oo=~0u>>2;
struct type
{
int x,y,z;
}A[1010];
struct edge
{
int t;
edge *next;
edge(int _t,edge *_next):t(_t),next(_next){}
}*Map[1010];
int N,ans1,ans2,pre[1010],f[1010];
bool vis[1010];
void addedge(int s,int t)
{
Map[s]=new edge(t,Map[s]);
}
int cmp(const void *a,const void *b)
{
if(((type *)a)->x>((type *)b)->x)
return 1;
return -1;
}
void dp()
{
for(int i=1;i<=N;i++)
f[i]=1;
for(int i=1;i<=N;i++)
for(int j=1;j<i;j++)
if(A[i].x>A[j].x&&A[i].y>A[j].y&&A[i].z>A[j].z)
{
if(f[j]+1>f[i])
f[i]=f[j]+1;
addedge(j,i);
}
for(int i=1;i<=N;i++)
ans1=max(ans1,f[i]);
}
bool solve(int u)
{
for(edge *p=Map[u];p;p=p->next)
{
int t=p->t;
if(vis[t])
continue;
vis[t]=true;
if(!pre[t]||solve(pre[t]))
{
pre[t]=u;
return true;
}
}
return false;
}
int main()
{
freopen("bomba.in","r",stdin);
freopen("bomba.out","w",stdout);
scanf("%d",&N);
for(int i=1;i<=N;i++)
scanf("%d%d%d",&A[i].x,&A[i].y,&A[i].z);
qsort(A+1,N,sizeof(A[0]),cmp);
dp();
ans2=N;
for(int i=1;i<=N;i++)
{
memset(vis,0,sizeof(vis));
ans2-=solve(i);
}
printf("%d\n%d\n",ans1,ans2);
return 0;
}