首页 > 代码库 > [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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。