ZOJ 1108 FatMouse's Speed (HDU 1160) DP

传送门：

ZOJ:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=108

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

题目大意：

输入好多组w 和 s 代表老鼠的重量和速度，要求找出满足 w 严格升序， s严格降序的最大长度和他们的序号。

我是先排序，然后和ZOJ 1136 Longest Ordered Subsequence (http://blog.csdn.net/murmured/article/details/14646445）一样。设dp [ i] 为以 i 结尾的升序列的最大值，那么从 i 开始向前查找，若 a[ j ]
< a [ i ] 则比较一下 dp的大小。

同时要存下序列。

虽然和题目的样例输出不一样，但这是正确的，因为解不唯一。题目也只要求一组解。

分析如图：

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

struct mouse

{

	int id;

	int weight;

	int speed;

}m[1024];

int dp[1024];

int data[1024][1024];

bool operator < (const mouse &a,const mouse &b)

{

	return a.weight < b.weight;

}

int main()

{

	int w,s,len=1;

	while(~scanf("%d%d",&w,&s))

	{

		m[len].id=len;

		m[len].weight=w;

		m[len].speed=s;

		len++;

	}

	sort(m,m+len);

	dp[1]=1;

	data[1][1]= m[1].id;

	for(int i=2;i<len;i++)

	{

		int temp=0;

		int index=i;

		for(int j=i-1;j>=1;j--)

		{

			if( m[j].speed > m[i].speed && m[i].weight!=m[j].weight)

			{

					if(temp < dp[j])

					{

						temp=dp[j];

						index=j;

					}

			}

		}

		dp[i]=temp+1;

		if(index!=i)

		{

			memcpy(data[i],data[index],sizeof(data[index]) );

			data[ i ][ dp[i] ] =  m[i].id;

		}

		else

			data[i][1]= m[i].id;

	}

	int ans=0,index=1;

	for(int i=1;i<len;i++)

	{

		if(ans< dp[i])

		{

				ans= dp[i] ;

				index= i;

		}

	}

	printf("%d\n",ans);

	for(int i=1;i<=ans;i++)

	{

		printf("%d\n",data[index][i]);

	}

	return 0;

}

巴特西

ZOJ 1108 FatMouse's Speed (HDU 1160) DP

最新文章

热门文章