记录编号	98010	评测结果	WWWWWWAAWW
题目名称	导弹拦截	最终得分	20
用户昵称	超级傲娇的AC酱	是否通过	未通过
代码语言	C++	运行时间	0.601 s
提交时间	2014-04-21 16:16:24	内存使用	0.32 MiB

/*
 Dirworh
 */
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
struct pos
{
    int x,y,z;
};
vector<pos>Pos;
int F1[1002],n,Path[1002];
bool v[1002];
int DP();
void Opt_V();
bool Jud();
void init();
 
int main()
{
	freopen("bomba.in","r",stdin);
	freopen("bomba.out","w",stdout);
    pos P;
    int i,j,Ans=0;
    cin>>n;
    init();for(i=0;i<n;i++)v[i]=false;
    for(i=0;i<n;i++)
    {
        cin>>P.x>>P.y>>P.z;
        Pos.push_back(P);
    }
    cout<<DP()<<endl;
	int Len=n,D;
    while(!Jud())
    {
	   D=DP();
	   Opt_V();
	   Len-=D;
	   Ans++;
    }
	cout<<Ans;
    return 0;
}
bool Jud()
{
	bool B=true;
	for(int i=0;i<n;i++)
		B=B&v[i];
	return B;
}
int DP()
{
	int i,j,loc=0,Max=0;
	for(i=1;i<n;i++)
    {
		if(!v[i])
            for(j=0;j<i;j++)
                if(Pos[i].x>Pos[j].x&&Pos[i].y>Pos[j].y&&Pos[i].z>Pos[j].z&&!v[j])
			    {
                    F1[i]=max(F1[j]+1,F1[i]);
				    Path[i]=j;
				    //标记数组v与路径数组p
				    /*
				    将每次路径上的节点进行标记。
				    并在v中标记，在DP时加上条件v
				    时间复杂度上界为n^3
				    */
			    }
	}
	//return *max_element(F1,F1+n);
	for(i=0;i<n;i++)
		if(F1[i]>Max&&!v[i])
			Max=F1[i],loc=i;
	return F1[loc];
}
void Opt_V()
{
	int i,loc=0,Max=0;
	for(i=0;i<n;i++)
		if(F1[i]>Max&&!v[i])
			Max=F1[i],loc=i;
	while(loc!=-1)//位置指向自身无法处理单元素情形
	{
		v[loc]=true;
		loc=Path[loc];
	}
}
void init()
{
	for(int i=0;i<=n;i++)F1[i]=1,Path[i]=-1;
}