選美大賽

Time Limit: 1000 MS Memory Limit: 65536 K Total Submit: 1099(318 users) Total Accepted: 349(252 users) Rating:? Special Judge:?No

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

3 2 1 2 3 1 2 3 0

Sample Output

The number is 2: 2 3 The number is 3: 1 2 3

#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <math.h> #include <limits.h> #include <map> #include <stack> #include <queue> #include <vector> #include <set> #include <string> #define ll long long #define ms(a) memset(a,0,sizeof(a)) #define pi acos(-1.0) #define INF 0x3f3f3f3f const double E=exp(1); const int maxn=1e6+10; using namespace std; int a[maxn]; int dp[maxn]; int vis[maxn]; int DP[maxn]; int main(int argc, char const *argv[]) {ios::sync_with_stdio(false);int n;while(cin>>n&&n){ ms(dp);ms(DP);ms(vis);for(int i=0;i<n;i++)cin>>a[i];int ans=INT_MIN;int res;for(int i=0;i<n;i++){dp[i]=1;for(int j=0;j<i;j++){if(a[i]>a[j]&&dp[i]<dp[j]+1){dp[i]=dp[j]+1;vis[i]=j;}}if(dp[i]>ans){ans=dp[i];res=i;}}int ress=res;int i=0;while(1){DP[i++]=vis[ress];ress=vis[ress];if(dp[ress]==1)break;}cout<<"The number is "<<ans<<":";for(int j=i-1;j>=0;j--)cout<<" "<<DP[j]+1;cout<<" "<<res+1<<endl;} return 0; }

?

轉載于:https://www.cnblogs.com/Friends-A/p/10324404.html

總結

以上是生活随笔為你收集整理的HURST 1116：选美大赛（LIS+路径输出）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。