FatMouse's Speed

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

最长递增子序列问题的一个变体。实际上跟最长递增子序列问题没有不论什么本质的差别。

定义一个结构体mice，设mice[i].w表示第i仅仅老鼠的重量，mice[i].s表示第i仅仅老鼠的速度。对mice结构体进行排序。以w为第一keyword，递增。s为第二keyword，递减。设dp[i]表示以mice[i]为结尾的最长序列的长度。考虑某一个dp[i]。则有：

dp[i] = max(dp[i], dp[j]+1) (1<=j<i，且mice[i].w>mice[j].w。mice[i].s < mice[j].s)

当中，初始条件为dp[i]=1 (i=1, 2, ..., n)

排序的过程中须要加一个变量记录其原始的位置，由于终于的输出是原始的排序。

贴上AC代码：

#include<iostream>

#include<algorithm>

using namespace std;

struct mouse

{

	int w;

	int s;

	int index;

};

    mouse mice[1005];

	int dp[1005];//dp[i]表示以mice[i]为结尾的最长递增子序列

    int pre[1005];//pre[i]记录i的上一个数据

    int res[1005];//存放终于的结果

bool cmp(mouse a,mouse b)

{

	if(a.w!=b.w)

	return a.w<b.w;

	return a.s>b.s;

}

int main()

{

    freopen("1160.in","r",stdin);

    freopen("1160.out","w",stdout);

	int i=1,j;

	while(cin>>mice[i].w>>mice[i].s)

	{

		dp[i]=1;

		pre[i]=0;

		mice[i].index=i;

		i++;

	}

	int n=i-1;

	sort(mice+1,mice+1+n,cmp);

	int maxlen=0;//最长序列长度

	int end;//最长序列的末尾下标

	dp[1]=1;

	for(i=1;i<=n;i++)

	{

		for(j=1;j<i;j++)

		{

			if(mice[i].w>mice[j].w&&mice[i].s<mice[j].s&&dp[j]+1>dp[i])

			{

				dp[i]=dp[j]+1;

				pre[i]=j;

				if(dp[i]>maxlen)

				{

					end=i;

					maxlen=dp[i];

				}

			}

		}

	}

	int t=end;

	i=0;

	while(t!=0)

	{

		res[i++]=t;

		t=pre[t];

	}

	cout<<i<<endl;//i指向总数

	while(i>0)

	{

		i--;

		cout<<mice[res[i]].index<<endl;

	}

	return 0;

}