从左向右,再从右向左各进行一次最长不XX序列,然后算出最大可以容纳人数,再用总人数减去就OK:)

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

相等的不能取考～～～～

a[i]存第i个人的身高

b[i]存以第i个人为终点的最长上升序列元素个数

b[i]=max{b[j]|a[i]>a[j]&1

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

n-最长不降子序列与最长不升子序列只和最大者+1即是解

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

测试数据 01：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 02：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 03：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 09：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 10：答案正确... 0ms

错误答案总是跟正确答案差１，怎么回事？

最长不降子序列 O(n^2logn)

交了3次

错在最长下降序列的生成上 f2[i]应该表示i-n的最长下降序列 而不是1-i的

两边求递增序列，然后求max。easy!

很搞笑的一个失误：

for i:=1 to n do

if b[i]+c[i]+1>max then max:=i;{应该是max:=b[i]+c[i]+1}

writeln(n-b[max]-c[max]-1);

这样也可以过5个数据……

动态规划

数组 a→记录高度 b[i]→到第i个人能排列最多的人数

对i个人进行枚举:

假设以i为最高，将数据分为(1..i)和(i..n)，分别动态规划。动态规划时先用1循环J（表示到J时的最大人数），里面再套个循环K计算到J的最大人数，同时不断跟新b[j]，记录下最大人数。动态规划后，将最大数汇总。

PS：大家想找这题有关的资料，可以上网找找里的'最长不下降序列'。

以前能很快解决这道题目。。。。

很奇怪现在不行了

注意是:n-k,我错了N次

f[i]表示从左到右最长上升子序列长度，

g[i]表示从左到右最长下降子序列长度。

tem:=max{ f[k]+max{g[k+1..n+1]} }

最后解为 n-tem

数据规模不大啊,直接枚举最高点就行了

DP基础题....最长不降/最长不升

两次DP，找左边最长上升和右边最长上升，再找最高点

做的第一道DP题，纪念一下

偶用两次DP～～

一次左到右的最长上升序列+一次右到左的最长上升序列+枚举最高点

c++代码
#include<bits/stdc++.h>
using namespace std;
int f[103],g[103],a[103],n,ans;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
f[1]=1;
for(int i=2;i<=n;i++){
f[i]=1;
for(int j=1;j<i;j++)
if(a[j]<a[i]) f[i]=max(f[i],f[j]+1);
}
g[n]=1;
for(int i=n-1;i>=1;i--){
g[i]=1;
for(int j=n;j>i;j--)
if(a[j]<a[i]) g[i]=max(g[i],g[j]+1);
}
for(int i=1;i<=n;i++) ans=max(ans,f[i]+g[i]-1);
printf("%d",n-ans);
return 0;
}