小乐乐大逃亡 | ||||||
| ||||||
Description | ||||||
小乐乐刚装完化妆品，突然大地摇晃，藏宝洞开始崩塌。小乐乐连忙往外跑，可原本的洞口居然出现了一条河！还好，河面上有一排高低不一的木桩，每个木桩上有一只地鼠。当踩了一个高度的木桩后，高度小于等于它的木桩和它左边的木桩都会全部崩塌。小乐乐看见地鼠十分生气，因为反应并不迅捷的她，每每玩打地鼠的游戏时，总有一种被地鼠玩弄的感觉（一个都没打到……啊哈哈哈哈哈……）。所以小乐乐想踩尽量多的地鼠，以解心头之挫败感……现在小乐乐想知道，她最多能踩扁几只地鼠？ | ||||||
Input | ||||||
第一行输入一个n（n<1000) | ||||||
Output | ||||||
输出小乐乐最多能踩扁的地鼠的个数 | ||||||
Sample Input | ||||||
7 | ||||||
Sample Output | ||||||
4 |
#include<stdio.h>
#include<string.h>
int main()
{
int dp[100000];
int a[100000];
int t;
while(~scanf("%d",&t))
{
memset(dp,0,sizeof(dp));
for(int i=0;i<t;i++)
{
scanf("%d",&a[i]);
}
int ans=0;
dp[0]=1;
for(int i=1;i<t;i++)
{
int max=0;
for(int j=0;j<i;j++)
{
if(a[i]>a[j]&&max<dp[j])max=dp[j];
}
dp[i]=max+1;
if(dp[i]>ans)ans=dp[i];
}
printf("%d\n",ans);
}
}