hdu1160 FatMouse's Speed

本题是dp+记录路径,数组pre用于存储其路径。
给出老鼠的体重和速度,求能使体重递增,速度递减的最长子序列(可不连续)
还要输出最长子序列的下标。
思路:
0.记录所给的每个重量和坐标,由于后面还要输出最长子序列的下标,所以我使用num记录每个下标。
1.先把输入的重量和速度按照重量从大到小排序,重量相等时按照速度从小到大排序。
2.排完序后,开始寻找按体重递增,速度递减的最长子序列:
由于sort已经排好顺序了,所以接下来如果找到第j只鼠符合mice[j].w>mice[i].w&&mice[j].s<mice[i].s
而且第j+1只鼠也符合mice[j].w>mice[i].w&&mice[j].s<mice[i].s,那么肯定第j只鼠比第j+1只鼠体重轻速度快。
3.第一层for循环控制长度,第二层for循环从0到i-1只鼠开始搜,如果符合条件,dp[i]=dp[j]+1;同时记录路径pre[i]=j;

关于状态转移方程dp[i]=dp[j]+1;dp[j]就是从0到j的最长符合题意的子序列的长度,dp[i]=dp[j]+1,符合j的子序列也符合i,
然后i在j的基础上又找到一个符合的,所以就dp[j]+1;

4.输出,先一个for循环遍历dp,找出最长的长度输出,记录最长长度的下标。
然后pre数组之前记录了路径,pre[i]=j就是j的前面是i,pos=pre[pos]就是把记录的pos的前一个下标赋值给pos,
以此类推直到pos=-1;(因为pre初始化就是-1嘛)


#include <string.h>
#include <stdio.h>
#include <math.h>
#include <queue>
#include <stack>
#include <algorithm>
#define ll long long
using namespace std;
const int maxn=1100;
int dp[maxn],pre[maxn];
struct node
{
	int w,s,num;
} mice[maxn];
bool cmp(node x,node y)
{
	if (x.w==y.w)
		return x.s<y.s;
	else
		return x.w>y.w;
}
int main()
{
	int i,j,n,len=0;
	while(scanf("%d%d",&mice[len].w,&mice[len].s)!=EOF)
	{
		mice[len].num=len+1;
		len++;
	}
	sort(mice,mice+len,cmp);
	memset(pre,-1,sizeof(pre)); 
	for (i=0; i<len; i++)
	{
		dp[i]=1;
		for (j=0; j<i; j++)
			if (mice[j].w>mice[i].w&&mice[j].s<mice[i].s)
				if (dp[j]+1>dp[i])
				{
					dp[i]=dp[j]+1;
					pre[i]=j;//记录路径,i->j
				}
	}

	int ans=-1,pos=0;
	for (i=0; i<len; i++)
		if (ans<dp[i])
		{
			ans=dp[i];
			pos=i;
		}
	printf("%d\n",dp[pos]);
	while(pos!=-1)
	{
		printf("%d\n",mice[pos].num);
		pos=pre[pos];
	}
	return 0;
}

上一篇:P1266 速度限制


下一篇:树莓派智能小车python3程序