posts - 99,  comments - 8,  trackbacks - 0
//解题思路:根据题意,要输出的是排序之前的序号,所以将要处理的数据都存入一个结构体中
//首先利用qsort对weight进行快排
//剩下的问题就是从已排好的数组中找到最长下降子列(speed),并且输出这个子列的长度和子列中的元素的下标

#include <stdio.h>
#include <stdlib.h>

struct mouse
{
  int w;
  int s;
  int cn;
}node[1001];
    
int cmp (const void *a, const void *b)  //一定要注意指针的指向是结构体      mouse
{
    if ( (*(mouse *)a).w != (*(mouse *)b).w )    //体重不等时对体重进行排序 
    return  (*(mouse *)a).w - (*(mouse *)b).w;
    
    else if ( (*(mouse *)a).w == (*(mouse *)b).w )
    return  (*(mouse *)b).s - (*(mouse *)a).s;  //反之对速度进行降序排序 
}

int main ()
{
    
    //输入数据
    int levl = 1;
    while (scanf ("%d%d", &node[levl].w, &node[levl].s) != EOF)                                            
    {
          node[levl].cn = levl;
          levl ++;
    }
    
    //快排
    qsort ( node, levl, sizeof(node[0]), cmp ); 
    
    //对speed 按降序找到最长的子串:
    //用数组F[i]记录以i为起点的满足条件的子列长度,显然初始时为1;
    //用rout[i]记录搜索到最长子串的路径 ,把路径的下标存入到index[]中 
    //max记录到当前为止子列的最长长度,end 记录到当前为止最长子列的最后一个下标
    int  F[1001]; 
    for (int i = 1; i < levl; i ++)
    {
        F[i] = 1;
    } 
    int rout[1001];
    for (int i = 1; i < levl; i ++)
    {
        rout[i] = i;
    }
    
    int max = 1;  int end = 1;
    for (int i = 2; i < levl; i ++)
    {
        for (int j = 1; j < i; j ++)
        {
            if (node[j].s > node[i].s)
            {
               if (F[j] + 1 > F[i])   //现在长度增加1要 > 当前F[i] 才能产生作用 
               {
                        F[i] = F[j] + 1;
                        rout[i] = j;                    //记录找到最下降序列的路径(即下标标号) 
               }
            }
        }
       
       if ( F[i] > max )  //当前记录的长度大于 >  max时 
        {
                max = F[i];
                end = i; 
        }
    }
    
    printf ("%d\n", max);
    
    int index[1001];
    for (int i = 0; i < max; i ++)             //将路径记录到数组index[]中 
    {
        index[max - i - 1] = end;
        end = rout[end--];
    } 
    
    for ( int i = 0; i < max; i ++)
    {
        printf ("%d\n", node[index[i]].cn);
    }
   // system ("pause");
    return 0;

posted on 2010-08-22 11:24 雪黛依梦 阅读(966) 评论(0)  编辑 收藏 引用 所属分类: 动态规划

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年8月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

留言簿(4)

随笔分类

随笔档案

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜