学步园

最长上升子序列，用记忆化搜索做的，比较慢。

代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int num, ver, cct;
int dp[32], path[30][30];
int save[30], box[30][10];
bool G[31][31];
int cmp(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}
bool Judge(int x, int y, int ver)
{
    for(int i=0; i<ver; ++i)
        if(box[x][i] >= box[y][i])
            return false;
    return true;
}
int d(int i)
{
    int &ans = dp[i];
    ans = 1;
    for(int j=0; j<num; ++j)
        if(G[i][j])
        {
            int dd = d(j) + 1;
            if(ans < dd)
                ans = dd;
        }
    return ans;
}
void print_ans(int i)
{
    save[cct++] = i + 1;
    for(int j=0; j<num; ++j)
        if( G[i][j] && (dp[i]==dp[j]+1) )
        {
            print_ans(j);
            break;
        }
}
int main()
{
    while(scanf("%d%d", &num, &ver) != EOF)
    {
        for(int i=0; i<num; ++i)
        {
            for(int j=0; j<ver; ++j)
                scanf("%d", &box[i][j]);
            qsort(&box[i], ver, sizeof(box[i][0]), cmp);
        }
        memset(G, false, sizeof(G));
        for(int i=0; i<num; ++i)
            for(int j=0; j<num; ++j)
                if((i!=j) && Judge(i, j, ver))
                {
                    G[i][j] = true;
                }
        memset(dp, 0, sizeof(dp));
        int Max = 0, imax;
        for(int i=0; i<num; ++i)
        {
            int ans = d(i);
            if(ans > Max)
            {
                Max = ans;
                imax = i;
            }
        }
        cct = 0;
        printf("%d\n", Max);
        print_ans(imax);
        printf("%d", save[0]);
        for(int i=1; i<cct; ++i)
            printf(" %d", save[i]);
        puts("");
    }
    return 0;
}