LIS有点小改动,比较的时候必须完全大于
#include<stdio.h>
#include<stdlib.h>
const int M=31;
int num[M][M], path[M], index[M];
int n, m, len;
int cmpnum(const void *a, const void *b)
{
return *(int *)a-*(int *)b;
}
int cmpindex(const void *a, const void *b)
{
return num[*(int *)a][0] - num[*(int *)b][0];
}
void print(int k, int lens)
{
if ( k < 0 || !len ) return;
print(path[k], len-1);
printf("%d", k+1);
len == lens ? putchar(10) : putchar(' ');
}
int judge(int j, int k)
{
for ( int i = 0 ; i < m ; i++ )
if ( num[j][i] <= num[k][i] )
return 0;
return 1;
}
int main()
{
while( 2 == scanf("%d%d", &n, &m) )
{
int dp[M], i, j;
for ( i = 0 ; i < n ; i++ )
{
index[i]= i; dp[i]= 1 ; path[i]= -1;
for ( j = 0 ; j < m ; j++ )
scanf("%d", num[i]+j);
qsort(num[i], m, sizeof(int), cmpnum);
}
qsort(index, n, sizeof(int), cmpindex);
int k= 0;
len= 1;
for ( i = 1 ; i < n ; i++ )
{
for ( j = 0 ; j < i ; j++ )
{
if ( judge(index[i], index[j]) && dp[i] < dp[j]+1 )
{
dp[i]= dp[j]+1;
path[index[i]]=index[j];
}
}
if (dp[i] > len)
{
len= dp[i];
k= index[i];
}
}
printf("%d\n", len);
print(k, len);
}
return 0;
}