#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int a[1005],b[1005],ans1=-99,ans2=-99,f[1005];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
f[1]=1;
for(int i=2;i<=n;i++)
{
for(int j=1;j<i;j++)
{
if(a[i]>=a[j]&&f[j]>f[i])
{
f[i]=f[j];
}
}
f[i]+=1;
}
for(int i=1;i<=n;i++)
{
if(f[i]>ans1)
ans1=f[i];
}
for(int i=1;i<=n;i++)
f[i]=0;
f[n]=1;
for(int i=n-1;i>0;i--)
{
for(int j=n;j>i;j--)
{
if(a[i]>=a[j]&&f[j]>f[i])
{
f[i]=f[j];
}
}
f[i]+=1;
}
for(int i=1;i<=n;i++)
{
if(f[i]>ans2)
ans2=f[i];
}
if(ans1>=ans2) cout<<n-ans1;
else cout<<n-ans2;
return 0;
}
by hllh @ 2018-06-25 15:39:24
@[MrLi](/space/show?uid=28195) 您不要这么发代码,根本看不懂,要么用代码插入,要么直接发截图
by SkyLiYu @ 2018-06-25 16:03:01
我记得这是个dp题目,你先推一下动态转移方程
by SkyLiYu @ 2018-06-25 16:03:52
```
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int a[1005],b[1005],ans1=-99,ans2=-99,f[1005];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
f[1]=1;
for(int i=2;i<=n;i++)
{
for(int j=1;j<i;j++)
{
if(a[i]>=a[j]&&f[j]>f[i])
{
f[i]=f[j];
}
}
f[i]+=1;
}
for(int i=1;i<=n;i++)
{
if(f[i]>ans1)
ans1=f[i];
}
for(int i=1;i<=n;i++)
f[i]=0;
f[n]=1;
for(int i=n-1;i>0;i--)
{
for(int j=n;j>i;j--)
{
if(a[i]>=a[j]&&f[j]>f[i])
{
f[i]=f[j];
}
}
f[i]+=1;
}
for(int i=1;i<=n;i++)
{
if(f[i]>ans2)
ans2=f[i];
}
if(ans1>=ans2)
{
if(ans1==n)
{
cout<<0;return 0;
}
else
cout<<n-ans1;
}
else cout<<n-ans2;
return 0;
}
```
by hllh @ 2018-06-25 16:09:55
@[隔壁小邱](/space/show?uid=22539) 转移方程和这个判断是一个意思
by hllh @ 2018-06-25 16:11:49
20分
by hllh @ 2018-06-25 16:12:16
@[MrLi](/space/show?uid=28195) 其他的点怎么样,WA?
by SkyLiYu @ 2018-06-25 16:21:51
@[MrLi](/space/show?uid=28195) 你回去读题去,我一眼看出一个错误
by SkyLiYu @ 2018-06-25 16:24:20