hdu 1160 FatMouse's Speed(最长上升子序列 +记录路径)

http://acm.hdu.edu.cn/showproblem.php?pid=1160

题意：有若干只老鼠，给出每只老鼠的大小和速度。输出尽量多的老鼠的下标m1,m2,m3......满足下标对应的老鼠大小严格递增而老鼠速度严格递减。

思路：先对老鼠的速度从大到小排序，在对老鼠的大小求最长上升子序列。在这过程中，用pre[ ]记录路径。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

struct node
{
    int size;
    int weight;
    int id;
    bool operator < (const struct node tmp)const
    {
    	if(weight == tmp.weight)
			return size < tmp.size;
        return weight > tmp.weight;
    }
}mice[1010];

int cnt,pre[1010],dp[1010];
int maxans,maxid;

void solve()
{
	memset(pre,-1,sizeof(pre));

	for(int i = 1; i <= cnt; i++)
	{
		dp[i] = 1;
		for(int j = 1; j < i; j++)
		{
			if(mice[j].size < mice[i].size && dp[i] < dp[j]+1)
			{
				dp[i] = dp[j]+1;
				pre[ mice[i].id ] = mice[j].id;	//记录路径
			}
		}
		if(maxans < dp[i])
		{
			maxans = dp[i];
			maxid = mice[i].id; //错写成maxid = i,Wa了几次.
		}
	}

	printf("%d\n",maxans);
	int ans[1010],count = 0;
	for(int t = maxid; t != -1; t = pre[t])
	{
		ans[count++] = t;
	}
	for(int i = count-1; i >= 0; i--)
		printf("%d\n",ans[i]);
}

int main()
{
    int s,w;
	cnt = 0;
    while(~scanf("%d %d",&s,&w))
        mice[++cnt] = (struct node){s,w,cnt};

	maxans = 0;
    sort(mice+1,mice+1+cnt);
    solve();

	return 0;
}

hdu 1160 FatMouse's Speed(最长上升子序列 +记录路径)

原文：http://blog.csdn.net/u013081425/article/details/19633245