嵌套矩形——DAG上的动态规划

嵌套矩形——DAG上的动态规划

#include "stdio.h"
#include "string.h"
#define N 1010
int a[N][2];
int b[N];

int main()
{
    int n,m,result;
    int i,j,temp,temp1,max;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d",&m);
        for(i=1;i<=m;i++)		//读入测试数据
        {
            scanf("%d%d",&temp,&temp1);
            a[i][0]=temp<temp1?temp:temp1;  //矩形的宽
            a[i][1]=temp<temp1?temp1:temp;	//矩形的长
        }

        //设置一个结构体  用 sort 即可
        for(i=1;i<=m;i++)	 //对矩形的宽进行由小到大排序
            for(j=i+1;j<=m;j++) if(a[i][0]>a[j][0])
                {temp=a[i][0];
                    a[i][0]=a[j][0];a[j][0]=temp;
                    temp1=a[i][1];a[i][1]=a[j][1];a[j][1]=temp1;}

        //求长进行最长升序列求解
        memset(b,0,sizeof(b)); result=0;
        for(i=m;i>0;i--)
        {
            max=0;
            for(j=i+1;j<=m;j++)
                if(a[j][1]>a[i][1] && a[j][0]>a[i][0]) max=max>b[j]?max:b[j];
            b[i]=max+1;

            result=result>b[i]?result:b[i];
        }

        printf("%d\n",result);
    }


    return 0;
}