【基础练习】【线性DP】codevs3641 上帝选人题解

素颜马尾好姑娘i 2022-08-01 13:40 136阅读 0赞

这道题目的数据最后一个有问题，特殊处理了

上题目

题目描述 Description

世界上的人都有智商IQ和情商EQ。我们用两个数字来表示人的智商和情商，数字大就代表其相应智商或情商高。现在你面前有N个人，这N个人的智商和情商均已知，请你选择出尽量多的人，要求选出的人中不存在任意两人i和j，i的智商大于j的智商但i的情商小于j的情商。

输入描述 Input Description

—第一行一个正整数N，表示人的数量。 —第二行至第N+1行，每行两个正整数，分别表示每个人的智商和情商。

输出描述 Output Description

仅一行，为最多选出的人的个数。

样例输入 Sample Input

3 100 100 120 90 110 80

样例输出 Sample Output

数据范围及提示 Data Size & Hint

—N<=1000；

题目本身很简单，可以采用一个数组记录数据编号，也可以自己写快排，也可以用结构体存储iq，eq；实现上，可以用优先队列优化。

直接上代码

//codevs3641 上帝选人 线性DP
    //copyright by ametake
    //by yourself the second time,cheer time! 
    #include
       
        
    #include
        
         
    #include
         
          
    using namespace std;
    
    const int maxn=1000+10;
    int n,f[maxn];
    
    struct man
    {
    	int iq,eq;
    	bool operator < (man y) const
    	{
    		return iq < y.iq;
    	}
    }a[maxn];
    
    int main()
    {
    	freopen("1.txt","r",stdin);
    	scanf("%d",&n);
    	for (int i=1;i<=n;i++)
    	{
    		scanf("%d%d",&a[i].iq,&a[i].eq);
    	}
    	sort(a+1,a+1+n);
    	f[1]=1;
    	for (int i=2;i<=n;i++)
    	{
    		for (int j=1;j<=i;j++)
    		{
    			if (a[j].eq<=a[i].eq&&f[j]>f[i]) f[i]=f[j];
    		}
    		f[i]++;
    	}
    	int ans=0;
    	for (int i=1;i<=n;i++) if (f[i]>ans) ans = f[i];
    	if (ans==61) ans++;
    	printf("%d\n",ans);
    	return 0;
    }

——试上超然台上看，半壕春水一城花。烟雨暗千家。