NYOJ－16－矩形ネスト

9338 ワード

記述にはn個の矩形があり、各矩形はa,bで記述でき、長さと幅を表す.矩形X(a,b)は、矩形Y(c,d)にネストすることができ、a面白い動帰題ですが、不安な私は別の方法でやってみたいと思って、WAのコードを書いて、感覚的には正しいですが、細かく味わって、致命的な間違いを発見しました.エラーコードは以下の通り(C):

//    ，        ，      ，             
//        ，              ，      （  ）      
//#include <stdio.h>
//#define MAX(a, b) a > b ? a : b
//#define MAXSIZEN 1001
//int t[MAXSIZEN] = {0};
//int ans;
//typedef struct
//{
// int a;
// int b;
//} rec; //  
//rec R[MAXSIZEN];
//
////    a[i] b[i]        t[j]
//void retrieve(int p, int n)
//{
// int q, i;
// q = 0;
// for(i = 1; i <= n; i++)
// {
// if(R[p].a > R[i].a && R[p].b > R[i].b)
// {
// if(t[i] > t[q])
// {
// q = i;
// }
// }
// }
// ans++;
// if(t[q])
// {
// retrieve(q, n);
// }
//}
//
//int main(int argc, const char * argv[])
//{
// int N;
// scanf("%d", &N);
// 
// while (N--)
// {
// ans = 1;
// int n, a, b;
// scanf("%d", &n);
// for (int i = 1; i <= n; i++)
// {
// scanf("%d %d", &a, &b);
// //      
// if (a > b)
// {
// R[i].a = b;
// R[i].b = a;
// }
// else
// {
// R[i].a = a;
// R[i].b = b;
// }
// }
// 
// int p = 0;
// for(int i = 1; i <= n; i++)
// {
// for(int j = 1; j <= n; j++)
// {
// if(R[i].a > R[j].a && R[i].b > R[j].b)
// {
// t[i]++;
// }
// }
// if(t[i] > t[p])
// {
// p = i;
// }
// }
// 
// retrieve(p, n);
// 
// printf("%d
", ans);
// }
//
// 
// return 0;
//}

この方法は貪欲なアルゴリズムに偏っているが、私は最も重要な問題を無視して、貪欲なアルゴリズムは後効果性が存在することができなくて、私の書き方は完璧にこの問題にぶつかった!!!
だから、別の動きを探して帰るしかない......

//  
#include <stdio.h>
#include <string.h>
#define MAX(a, b) a > b ? a : b
#define MAXSIZEN 1001
int dp[MAXSIZEN];   //dp[i]      i           i      
int ans;
typedef struct
{
    int a;
    int b;
} rec;  //  

int main(int argc, const char * argv[])
{
    int N;
    scanf("%d", &N);
    rec R[MAXSIZEN];

    while (N--)
    {
        ans = 1;
        memset(dp, 0, sizeof(dp));
        int n, a, b;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
        {
            scanf("%d %d", &a, &b);
            //      
            if (a > b)
            {
                R[i].a = b;
                R[i].b = a;
            }
            else
            {
                R[i].a = a;
                R[i].b = b;
            }
        }

        //      
        for (int i = 1; i < n; i++)
        {
            for (int j = i + 1; j <= n; j++)
            {
                if (R[i].a > R[j].a || (R[i].a == R[j].a && R[i].b > R[j].b))
                {
                                        R[i].a ^= R[j].a;
                                        R[j].a ^= R[i].a;
                                        R[i].a ^= R[j].a;
// R[i].a ^= R[j].a ^= R[i].a ^= R[j].a;
                                        R[i].b ^= R[j].b;
                                        R[j].b ^= R[i].b;
                                        R[i].b ^= R[j].b;
// R[i].b ^= R[j].b ^= R[i].b ^= R[j].b;
                }
            }
        }

        int flag;
        for (int i = 1; i <= n; i++)
        {
            dp[i] = 1;
            flag = 0;
            for (int j = 1; j < i; j++)
            {
                if (R[j].a < R[i].a && R[j].b < R[i].b && dp[j] > flag)
                {
                    flag = dp[j];
                }
            }
            dp[i] += flag;
        }

        for (int i = 1; i <= n; i++)
        {
            if (ans < dp[i])
            {
                ans = dp[i];
            }
        }

        printf("%d
", ans);
    }

    return 0;
}

ACコード、おお++!!!

【C】——treeコマンドの実装

miniチケット販売システムの作成スレッドの3つの方法