/*先对第一关键字升序排序后再对第二关键字求最长下降子序列*/

#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

#define MAXN 5005

struct node
{
	int len;
	int wei;
}per[MAXN] = {0};

int dp[MAXN];

bool cmp(node a,node b)
{
	return (a.len <= b.len);
}

int main()
{
	int T,i,j,n;
	cin>>T;
	while(T)
	{
		cin>>n;
		for(i = 1;i <= n;i ++)
			scanf("%d %d",&per[i].len,&per[i].wei);
		sort(per+1,per+n+1,cmp);
		for(i = 1;i <= n;i ++)
		{
			dp[i] = 1;
			for(j = 1;j < i;j ++)
				if(per[j].wei > per[i].wei && dp[j] + 1 > dp[i])
					dp[i] = dp[j] + 1;
		}
		int Max = 0;
		for(i = 1;i <= n;i ++)
			Max = max(Max,dp[i]);
		cout<<Max<<endl;
		T --;
	}
	return 0;
}

• Re:动态规划，最长下降子序列问题 (140) 3435973836 2016-02-26 21:35:54
  • Re:动态规划，最长下降子序列问题 (202) 3435973836 2016-02-26 21:50:26
• Re:动态规划，最长下降子序列问题 (46) ksqsf 2017-10-01 16:19:35