HLG1116-选美大赛

Description

一年一度的哈理工选美大赛开始了.来自各个院系的N个美女们都在一起排成一排，然后从左到右给他们标号(1-N),评委叫兽开始观摩,由于身高高低都不同, 叫兽想从中选出尽可能多的人使得他们的身高从左到右依次递增，你能帮助叫兽吗？

Input

输入数据第一行一个数据表示美女的个数N(0<N<100)

接下来有N个数据表示1-N标号的美女的身高，身高范围都在0-180之内

当N=0时候输入结束

Output

按照样例输出，首先The number is N：N是选出最多美女个数,然后后面输出N个数，代表选出美女的标号,从左到右依次输出.

题目保证答案唯一

Sample Input

2 1 2

1 2 3

Sample Output

The number is 2: 2 3

The number is 3: 1 2 3

想说，这道题目，求LIS不是问题，纠结在于记录路径，搞这个搞了半天，结果还是去看了大牛的博客T T，只能说，学习了。。。

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <iostream>

 #include <stack>

 using namespace std;

 const int MAX_SIZE = ;

 int dp[MAX_SIZE];

 int vis[MAX_SIZE];

 int strat;

 int LIS(int arr[], int n)

 {

     memset(vis, , sizeof(vis));

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

     {

         dp[i] = ;

     }

     int ans = ;

     dp[] = ;

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

     {

         ans = dp[i];

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

         {

             if(arr[i] > arr[j] && dp[j] > ans)

             {

                 ans = dp[j];

                 vis[i] = j;

             }

         }

         dp[i] = ans + ;

     }

     ans = ;

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

     {

         if(dp[i] > ans)

         {

             ans = dp[i];

             strat = i;

         }

     }

     return ans;

 }

 ///dfs去找路径

 void path(int strat)

 {

     if(strat != )

     {

         path(vis[strat]);

         printf(" %d", strat);

     }

 }

 int main()

 {

     int n;

     int arr[MAX_SIZE];

     stack<int > s;

     while(~scanf("%d", &n) && n)

     {

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

         {

             scanf("%d", arr + i);

         }

         int ans = LIS(arr, n);

         printf("The number is %d:",ans);

         path(strat);

         puts("");

     }

     return ;

 }

巴特西

HLG1116-选美大赛

最新文章

热门文章