矩形嵌套 DP 南阳理工 http://acm.nyist.net/JudgeOnline/problem.php?pid=16

刚开始用DP、贪心都没有AC,后来看看书上讲的有知识，才发现自己错了。矩形之间的关系是典型的二元关系，二元关系可以用图来建模。如果X可以镶嵌在Y里，我们就从X到Y连一条有向边。只要求这个图上的最长路径即可。

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>

using namespace std;
typedef struct {
        int a;
        int b;
        }data;
data A[1000];
int a[1000][1000];
int b[1000];
int n;
void map(int n)
{   memset(a,0,sizeof(a));
    for(int i=0; i<n; i++)
    scanf("%d %d",&A[i].a,& A[i].b);
    for(int i=0; i<n; i++)
    for(int j=0;j<n; j++)
    if( (A[i].a>A[j].a && A[i].b>A[j].b)||(A[i].a>A[j].b && A[i].b>A[j].a))
    a[i][j]=1;
    
}
int dp(int i)
{
    int & ans =b[i];
    if(ans > 0) return ans;
    ans =1;
    for(int j=0; j<n; j++)
    if(a[i][j]) 
    {
     if(ans<dp(j)+1)
     ans = dp(j)+1;
    }
    return ans;
}
int main()
{
     int N;
    scanf("%d",&N);
    while(N--)
    {
      scanf("%d",&n);
      memset(b, 0, sizeof(b));
      map(n);
      int t = 0;
      for(int i=0; i<n; i++)
      if(dp(i)>t) t = dp(i);
      printf("%d\n",t);
    }
   system("pause");
   return 0;
}

更多相关文章

随机推荐