HDU 1160 동적 계획

/*
동적 기획의 세 번째 문제입니다.작은 세부 사항 하나를 하루 종일 생각했더니 다른 사람의 코드를 비교해 보니 마침내 발견되었다.
*/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <iomanip>
using namespace std;
struct mouse
{
	int w;
	int v;
	int num;
}mice[1005];
int dp[1005],fa[1005],father[1005],flag = 1;
int cmp(mouse m1,mouse m2)
{
    if(m1.w==m2.w)return m1.v>m2.v;
	return (m1.w<m2.w)?1:0;
}
void set(int *fa, int k)
{
    if(k==0)
        return ;
    father[flag++] = k;
    set(fa,fa[k]);
}

int main(int argc, char *argv[])
{
	int n = 0;
	while(scanf("%d%d",&mice[n].w,&mice[n].v)!=EOF)
	{
		mice[n].num = n+1;
		++n;
	}
	sort(mice,mice+n,cmp);
	memset(dp,0,sizeof(dp));

	dp[0] = 1;
	int k = 0,ans = 1;
	for(int i = 1; i < n; i++)
	{
	    dp[i] = 1;
		for(int j = 0; j < i; j++)
		{
			if(mice[j].w<mice[i].w&&mice[j].v>mice[i].v&&dp[j]+1>dp[i])
			{
				fa[mice[i].num] = mice[j].num;
				dp[i] = dp[j]+1;
			}
		}
		if(ans<dp[i])
		{
			ans = dp[i];
			k = mice[i].num;
		}

	}
	printf("%d
",ans);
	set(fa,k);//    
	for(int i = ans; i >= 1; i--)//    
    {
         printf("%d",father[i]);
         if(i!=1)
         printf("
");
    }
	return 0;
}