F

admin管理员组

文章数量:1794759

F

malic.xyz竞赛03 - Virtual Judge

开发商计划在海边建造许多海景房的楼房，工程师发现在设计图中由于某些靠海的楼太高，导致有些稍远的楼房即使站在楼顶也不能看到海。开发商和工程师就在分析，只能在原设计图中保留一部分楼，才能保证所有的楼都可以在楼顶看到海。若两楼的高度相同，也认为可以在楼顶看到海。

按离海岸的距离从远到近的给出各楼在设计图上的高度，请你计算开发商最多可以建多少幢海景房

input

输入有两行，第一行是设计图中的楼房数量N，第二行有N个正整数hi，表示各楼在设计图上的高度。

• 1 < N ≤ 25
• 1≤hi≤232

9
400 307 255 400 399 270 258 65 290

output

输出1行一个整数，代表开发商最多可以保留下的海景房的数量

6

代码

#include<bits/stdc++.h>
using namespace std;
int height[26];
int dp[26];void renew(int n){int max=0;for(int i=0;i<n;i++){if(height[i]>=height[n]&&dp[i]>max) max=dp[i];}dp[n]+=max;
}int main(){int n,temp,ans=0;cin>>n;for(int i=0;i<n;i++){cin>>height[i];dp[i]=1;}for(int i=0;i<n;i++){renew(i);if(dp[i]>ans) ans=dp[i];}cout<<ans;
}

本文标签： F