hdu 1160 FatMouse's Speed 解题报告

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1160

题目意思：给出一堆老鼠，假设有 n 只（输入n条信息后Ctrl+Z）。每只老鼠有对应的weight 和 speed。现在需要从这 n 只老鼠的序列中，找出最长的一条序列，满足老鼠的weight严格递增，speed严格递减。

我们可以用一个结构体来保存老鼠的信息，包括weight, speed 以及 id（这个 id 是未排序之前的，为了输出最后信息）。那么首先对 weight 进行递增排序，如果遇到相同的weight，就对speed进行递减排序。那么固定了weight，我们就可以着眼于对speed的处理，此时问题就变成求最长递减序列啦。由于要保存路径信息，代码用path[]来保存，递归输出即可。

这条题目拖了好久啊，差不多一年了= =，太懒～～～

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int maxn =  + ;

 struct node

 {

     int id;

     int weight, speed;

 }mouse[maxn];

 int path[maxn];

 int cnt[maxn];

 int cmp(node a, node b)

 {

     if (a.weight == b.weight)

         return a.speed > b.speed;

     return a.weight < b.weight;

 }

 void output(int pos)

 {

     if (!path[pos])

         return;

     output(path[pos]);

     printf("%d\n", path[pos]);

 }

 int main()

 {

     int w, sp, len = ;

     #ifndef ONLINE_JUDGE

         freopen("in.txt", "r", stdin);

     #endif

     while (scanf("%d%d", &w, &sp) != EOF)

     {

         mouse[len].weight = w;

         mouse[len].speed = sp;

         mouse[len].id = len;

         cnt[len++] = -;

     }

     sort(mouse+, mouse+len, cmp);

     for (int i = ; i < len; i++)

     {

         int k = ;

         for (int j = ; j < i; j++)

         {

             if (mouse[j].speed > mouse[i].speed && mouse[j].weight < mouse[i].weight && k < cnt[j])

             {

                 k = cnt[j];

                 path[mouse[i].id] = mouse[j].id;

             }

         }

         cnt[i] = k;

         cnt[i]++;

     }

     int ansid, ans = -;

     for (int i = ; i < len; i++)

     {

         if (cnt[i] > ans)

         {

             ans = cnt[i];

             ansid = mouse[i].id;

         }

     }

     printf("%d\n", ans);

     output(ansid);

     printf("%d\n", ansid);

     return ;

 }

巴特西

hdu 1160 FatMouse's Speed 解题报告

最新文章

热门文章