hdu1160 FatMouse's Speed 最长上升子序列以及记录路径 DP


FatMouse's SpeedTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5102    Accepted Submission(s): 2222
Special Judge

Problem DescriptionInputOutputSample InputSample Output

题目大意是找到一个最多的老鼠序列，使得序列中的老鼠的体重满足递增，相应老鼠的速度满足递减。思路就是先按体重递增进行sort排序，然后按照体重找到最长递减子序列即可，用动态规划做比较简单。状态f[i]表示前i个老鼠中的最长递减子序列长度，状态转移方程为f[i] = max{f[j], mice[j].speed > mice[i].speed} + 1, 最后找出最大的f[i]即可。注意此题还需要输出找到的序列中的老鼠的最原始的标号，因此不仅要在刚开始的时候把每个老鼠的最初的序号记下来，还要在进行状态转移的时候把当前的老鼠的位置标记下来。

 

#include<stdio.h>#include<string.h>#include<stdlib.h>struct haha{ int wei; int spe; int num;}a[1010];int cmp(const void *a,const void *b){ if((*(struct haha *)a).wei!=(*(struct haha *)b).wei) return (*(struct haha *)a).wei-(*(struct haha *)b).wei; else return (*(struct haha *)b).spe-(*(struct haha *)a).spe;}int l[1010],pre[1010],ans[1010];//l是记录的长度 pre记录的是路径int main(){ int cnt=1,i,j,max_l=0,end;      while(scanf("%d %d",&a[cnt].wei,&a[cnt].spe)!=EOF)   {    a[cnt].num=cnt++;   }   qsort(a+1,cnt-1,sizeof(struct haha),cmp);   for(i=1;i<cnt;i++) {l[i]=1;pre[i]=0;}      for(i=1;i<cnt;i++)   {    for(j=1;j<i;j++)    {         if(a[i].wei>a[j].wei&&a[i].spe<a[j].spe&&l[i]<l[j]+1)      {       l[i]=l[j]+1;       pre[i]=j;//这里面记录的是倒序 后面要倒着输出      }    }   }   end=1;   max_l=l[1];   for(i=2;i<cnt;i++) if(max_l<l[i]) {max_l=l[i];end=i;}   printf("%d\n",max_l);   for(i=1;i<cnt;i++)//记录下来  方便倒着输出   {            ans[i]=end;       end=pre[end];   }   for(i=max_l;i>=1;i--)   {             printf("%d\n",a[ans[i]].num);   }     return 0;   }