機器人軍團
時間限制: 1 Sec 內存限制: 64 MB
提交: 279 解決: 139
[提交] [狀態] [命題人:admin]
題目描述
邪狼：“怎么感覺這些機器人比我還聰明？不是說人工智能永遠不能超越人類嗎？”

天頂星人：“你們真是目光短淺，自大而愚蠢！你要知道，如果有意識的智慧生命在無窮無盡的歲月里居然做不到無意識的宇宙曾做過的事（產生智慧生命），這就好像一只無知的猴子在琴鍵上跳了億萬年居然跳出了一支貝多芬第九交響曲，而有智慧的生物居然幾千年也學不會一支簡單的小夜曲那樣荒謬。如果說永遠都做不到，那這在你們的哲學里，不就是神秘論和不可知論了嗎？要知道世事無絕對。”

話說在天頂星人的指導下，修羅王建造了一支機器人軍團，機器人排成一行，且身高分別為b1，b2，…，bn。修羅王準備從中選出一組滿足最長不下降子序列規則的機器人組成一支精銳衛隊。所謂不下降子序列（Longest Increasing Subsequence，LIS）定義為：設有由n個不相同的整數組成的數列b[n]，若有下標i1<i2<…<iL且b[i1]<b[i2]<…<b[iL]，則稱存在一個長度為L的不下降序列。

例如13，7，9，16，38，24，37，18，44，19，21，22，63，15。有13<16<38<44<63 長度為5的不下降子序列。但經過觀察，實際還有7<9<16<18<19<21<22<63 長度為8的不下降子序列。那么是不是還有更長的不下降子序列呢?請找出最長不下降子序列的長度。

輸入
第一行為n，表示n(n≤100000)個數。第二行為n個數的值。

輸出
一個整數，即最長不下降序列的長度。

樣例輸入
復制樣例數據
4
1 3 1 2
樣例輸出
2

解題思路：
用$dp[i]$來代表以$i$結尾的最長上升子序列的最大長度。
因此，對于每一次更新$dp[i]$時，僅需從開始遍歷到$i$，如果遍歷的值會小于$arr[i]$，更新依次$dp[i]$即可，即
$dp[i]=max(dp[i],dp[j]+1)$$(i:1$~ $n,j:1$~ $i?1)$

代碼：

//#pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <set>
#include <utility>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define lep(i,l,r) for(int i=l;i>=r;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
//priority_queue<int,vector<int> ,greater<int> >q;
const int maxn = (int)1e5 + 5;
const ll mod = 1e9+7;
int arr[100100];
int dp[100100];
int main() 
{#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);#endif//freopen("out.txt", "w", stdout);//ios::sync_with_stdio(0),cin.tie(0);int n;scanf("%d",&n);rep(i,1,n) {scanf("%d",&arr[i]);dp[i]=1;}int ans=0;rep(i,1,n) {for(int j=1;j<i;j++) {if(arr[j]<arr[i]) {dp[i]=max(dp[i],dp[j]+1);}}}rep(i,1,n) {ans=max(ans,dp[i]);}printf("%d\n",ans);return 0;
}