小乐乐大逃亡 Time Limit: 1000 MS Memory Limit: 32768 K Total Submit: 188(94 users) Total Accepted: 103(92 users) Rating: Special Judge: No
Description 小乐乐刚装完化妆品，突然大地摇晃，藏宝洞开始崩塌。小乐乐连忙往外跑，可原本的洞口居然出现了一条河！还好，河面上有一排高低不一的木桩，每个木桩上有一只地鼠。当踩了一个高度的木桩后，高度小于等于它的木桩和它左边的木桩都会全部崩塌。小乐乐看见地鼠十分生气，因为反应并不迅捷的她，每每玩打地鼠的游戏时，总有一种被地鼠玩弄的感觉（一个都没打到……啊哈哈哈哈哈……）。所以小乐乐想踩尽量多的地鼠，以解心头之挫败感……现在小乐乐想知道，她最多能踩扁几只地鼠？ Input 第一行输入一个n（n<1000) 之后一行有n个数，表示木桩的高度
Output 输出小乐乐最多能踩扁的地鼠的个数 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]; } PRintf("%d/n",ans); }}新闻热点
疑难解答
