HDOJ 1160 FatMouse's Speed

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

typedef struct s_mouse{
	int id;
	int weight;
	int speed;
}s_mouse;

static s_mouse mice[1000];
static int m[1000];
static int s[1000];
//static int p[1000];

static int num;

int m_compare(const void *a,const void *b)
{
	s_mouse *a_m=(s_mouse *)a;
	s_mouse *b_m=(s_mouse *)b;
	if(a_m->weight == b_m->weight
		&&	a_m->speed == b_m->speed)
		return 0;
	if(a_m->weight < b_m->weight
		|| a_m->weight == b_m->weight && a_m->speed > b_m->speed)
		return -1;
	return 1;
}

static void fat_mouse()
{
	//1. sort
	qsort(mice,num,sizeof(s_mouse),m_compare);

	//2. Dynamic Programming
	//2.1 initialize
	m[num-1]=1;
	s[num-1]=0;
	//2.2 scan
	int i,j;
	for(i=num-2;i>=0;i--){
		int max=1;
		int maxi=0;
		for(j=num-1;j>i;j--){
			if(mice[i].weight<mice[j].weight && 
				mice[i].speed>mice[j].speed){
				if(max<m[j]+1){
					max=m[j]+1;
					maxi=j;
				}
			}
		}
		m[i]=max;
		s[i]=maxi;
	}
}

int main(int argc,char *argv[])
{
	int i;
	for(i=0;scanf("%d%d",&mice[i].weight,&mice[i].speed)>0;i++)
		mice[i].id=i+1;
	num=i;
	fat_mouse();
	int max_index=0;
	for(i=num-1;i>0;i--)
		if(m[i]>m[max_index])
			max_index=i;
	printf("%d\n",m[max_index]);
	for(i=max_index;s[i]!=0;){
		printf("%d\n",mice[i].id);
		i=s[i];
	}
	printf("%d\n",mice[i].id);
	return 0;
}