小樂樂大逃亡 Time Limit: 1000 MS Memory Limit: 32768 K Total Submit: 188(94 users) Total Accepted: 103(92 users) Rating: Special Judge: No
Description 小樂樂剛裝完化妝品，突然大地搖晃，藏寶洞開始崩塌。小樂樂連忙往外跑，可原本的洞口居然出現(xiàn)了一條河！還好，河面上有一排高低不一的木樁，每個木樁上有一只地鼠。當(dāng)踩了一個高度的木樁后，高度小于等于它的木樁和它左邊的木樁都會全部崩塌。小樂樂看見地鼠十分生氣，因為反應(yīng)并不迅捷的她，每每玩打地鼠的游戲時，總有一種被地鼠玩弄的感覺（一個都沒打到……啊哈哈哈哈哈……）。所以小樂樂想踩盡量多的地鼠，以解心頭之挫敗感……現(xiàn)在小樂樂想知道，她最多能踩扁幾只地鼠？ Input 第一行輸入一個n（n<1000) 之后一行有n個數(shù)，表示木樁的高度
Output 輸出小樂樂最多能踩扁的地鼠的個數(shù) Sample Input 7 1 7 3 5 9 4 8 Sample Output 4 Author tju
#include<stdio.h> ///求最長遞增子序列 #include<string.h>#include<iostream>using namespace std;int main(){ int n; int a[1005]; int dp[1005]; while(~scanf("%d",&n)) { for(int i=0;i<n;i++) { scanf("%d",&a[i]); } int ans=1; dp[0]=1; for(int i=1;i<n;i++) { int maxi=0; for(int j=0;j<i;j++) { if(a[j]<a[i]&&maxi<dp[j]) maxi=dp[j]; } dp[i]=maxi+1; if(ans<dp[i]) ans=dp[i]; }新聞熱點
疑難解答
