比赛 20140421 评测结果 WWWWWWWAWA
题目名称 导弹拦截 最终得分 20
用户昵称 digital-T 运行时间 0.328 s
代码语言 C++ 内存使用 0.31 MiB
提交时间 2014-04-21 10:28:59
显示代码纯文本
  1. #include<cstdio>
  2. #include<cstring>
  3. #include<cmath>
  4. #include<algorithm>
  5. #include<vector>
  6. using namespace std;
  7. int N;
  8. class Point
  9. {
  10. public:
  11. int x,y,z;
  12. }p[1010];
  13. int f[1010];
  14. bool cmp(Point a,Point b)
  15. {
  16. if(a.x!=b.x)return a.x<b.x;
  17. if(a.y!=b.y)return a.y<b.y;
  18. return a.z<b.z;
  19. }
  20. bool vis[1010]={0};
  21. int match[1010]={0};
  22. bool find(int u)
  23. {
  24. vis[u]=true;
  25. for(int v=1;v<=N;v++)
  26. if(f[v]-f[u]==1)
  27. {
  28. if(vis[v])continue;
  29. vis[v]=true;
  30. if(match[v]==0 || find(match[v]))
  31. {
  32. match[v]=u;
  33. match[u]=v;
  34. return true;
  35. }
  36. }
  37. return false;
  38. }
  39. int main()
  40. {
  41. freopen("bomba.in","r",stdin);
  42. freopen("bomba.out","w",stdout);
  43. scanf("%d",&N);
  44. for(int i=1;i<=N;i++)
  45. scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z);
  46. sort(p+1,p+N+1,cmp);
  47. f[N]=1;
  48. for(int i=N-1;i>=1;i--)
  49. {
  50. f[i]=1;
  51. for(int j=i+1;j<=N;j++)
  52. if(p[i].x<p[j].x && p[i].y<p[j].y && p[i].z<p[j].z)
  53. f[i]=max(f[i],f[j]+1);
  54. }
  55. int Ans=0;
  56. for(int i=1;i<=N;i++)
  57. Ans=max(Ans,f[i]);
  58. printf("%d\n",Ans);
  59. int Ans_2=N;
  60. for(int i=1;i<=N;i++)
  61. {
  62. memset(vis,false,sizeof(vis));
  63. Ans_2-=find(i);
  64. }
  65. printf("%d\n",Ans_2);
  66. return 0;
  67. }