NOJ 16题 矩形嵌套 DP（单调递增子序列）

本文主要是介绍NOJ 16题 矩形嵌套 DP（单调递增子序列），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接~~>

本题为简单DP，需用单调递增子序列，不废话了一切尽在代码中。

 

代码：

#include<stdio.h>
#include<algorithm>
using namespace std;
int dp[1005];
struct zhang
{int x,y;
}t[1005];
bool cmp(const zhang &a,const zhang &b)
{return a.x < b.x ;
}
int main()
{int T,i,j,max,a,b,n,q;scanf("%d",&T);while(T--){scanf("%d",&n);max=0;for(i=0;i<n;i++){scanf("%d%d",&a,&b);if(a>b){q=a;a=b;b=q;}t[i].x=a;t[i].y=b;}sort(t,t+n,cmp);for(i=0;i<n;i++){dp[i]=1;for(j=0;j<i;j++)if(t[i].x>t[j].x&&t[i].y>t[j].y&&dp[j]+1>dp[i])dp[i]=dp[j]+1;if(max<dp[i])max=dp[i];}printf("%d\n",max);}return 0;
}

 

这篇关于NOJ 16题 矩形嵌套 DP（单调递增子序列）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---