Source Code

Problem: 1836		User: AllenYi
Memory: 160K		Time: 63MS
Language: C++		Result: Accepted
Source Code


#include <iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int dp[1005],n;
int dp2[1005];
float height[1005];

void solve()
{
    dp[0]=1;
    for(int i=1;i<n;++i)
    {
        dp[i]=1;
        for(int j=0;j<i;++j)
        {
            if(height[j]<height[i])
                dp[i]=max(dp[i],dp[j]+1);
        }
    }
    for(int i=1;i<n;++i)
        dp[i]=max(dp[i],dp[i-1]);
    dp2[n-1]=1;
    for(int i=n-2;i>=0;--i)
    {
        dp2[i]=1;
        for(int j=n-1;j>i;--j)
        {
            if(height[j]<height[i])
                dp2[i]=max(dp2[i],dp2[j]+1);
        }
    }
    for(int i=n-2;i>=0;--i)
        dp2[i]=max(dp2[i],dp2[i+1]);
    int res=0x3f3f3f3f;
    for(int i=1;i<n;++i)
    {
        int tmp=n-dp[i-1]-dp2[i];
        if(res>tmp)
            res=tmp;
    }

    printf("%d\n",res);
}


int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0;i<n;++i)
           scanf("%f",height+i);
        solve();
    }
    return 0;
}

• Re:英语本来不好，example还是错的 更加难理解了，example答案是3啊，顺便给个n^2的代码 (21) liojing 2014-08-27 09:52:34