矩形ネスト(dp水題)


長方形のネスト

  • タイトルの説明:
    長さと幅を表すn個の矩形があり、各矩形はa,bで記述することができる.矩形X(a,b)は、矩形Y(c,d)にネストすることができ、aのみ
    説明を入力:
             N(0 
        

    出力の説明:
                ,             ,       

    サンプル入力:
    コピー
    1
    10
    1 2
    2 4
    5 8
    6 10
    7 9
    3 1
    5 8
    12 10
    9 7
    2 2
    

    サンプル出力:
    5

    構想:まず入力を大きくて幅が小さくなって、それから長い列を作って、それから最も長い増分子のシーケンスを持って、acすることができます;
    #include 
    #include 
    #include 
    using namespace std;
    const int mn = 1005;
    int dp[mn];
    struct node
    {
        int x, y;
    }t[mn];
    bool cmp(node x, node y)
    {
        return x.x < y.x;
    }
    int main()
    {
        int i, j, n, m, x, y;
        scanf("%d",&m);
        while (m--)
        {
            scanf("%d",&n);
            for(i = 1;i <= n;i++)
            {
                scanf("%d%d",&x,&y);
                t[i].x = max(x,y);
                t[i].y = min(x,y);
            }
            sort(t+1,t+n+1,cmp);
            int maxx = 0;
            for (i = 1;i <= n;i++)
            {
                dp[i] = 1;
                for (j = 1;j < i;j++)
                {
                    if (t[j].y < t[i].y && t[i].x > t[j].x)
                        dp[i] = max(dp[i],dp[j]+1);
                }
                maxx = max(maxx,dp[i]);
            }
            printf("%d
    ",maxx); } return 0; }