首页 > 代码库 > [HDU1160]FatMouse's Speed

[HDU1160]FatMouse's Speed

题目大意:读入一些数(每行读入$w[i],s[i]$为一组数),要求找到一个最长的序列,使得符合$w[m[1]] < w[m[2]] < ... < w[m[n]]$且$s[m[1]] > s[m[2]] > ... > s[m[n]]$,并输出每组数在读入时的顺序具体见原题目

思路:先根据w从小到大排序,再求最长下降子序列,DP时保存路径,最后递归输出路径。

C++ Code:

 

#include<cstdio>#include<algorithm>#include<string.h>using namespace std;int n=1;struct sz{	int w,s,num;	bool operator <(const sz& rhs)const{		if(w!=rhs.w)return w<rhs.w;		return s>rhs.s;	}}a[1020];int d[1020],p[1020];void dg(int n){	if(n==0)return;	dg(d[n]);	printf("%d\n",a[n].num);}int main(){	while(scanf("%d%d",&a[n].w,&a[n].s)!=EOF)a[n].num=n,n++;	n--;	sort(a+1,a+n+1);	memset(d,0,sizeof(d));//d[i]表示i的前一个数 	memset(p,0,sizeof(p));//p[i]表示以s[i]结尾的最长下降子序列的长度 	for(int i=1;i<=n;i++)p[i]=1;	for(int i=2;i<=n;i++){		for(int j=1;j<i;j++)		if(a[i].w>a[j].w&&a[i].s<a[j].s){//a[i].w>a[j].w不能去掉,因为可能出现两个w相等的情况 			if(p[i]<p[j]+1){				p[i]=p[j]+1;				d[i]=j;			}		}	}	int t,max=0;	for(int i=1;i<=n;i++)	if(max<p[i]){		t=i;		max=p[i];	}	printf("%d\n",max);	dg(t);	return 0;}

 

  

 

[HDU1160]FatMouse's Speed