先看答案,再思考
#include<iostream>
using namespace std;
int main(){
int n;cin>>n;
int a[1010] , f[1010] , g[1010];
for(int i = 0 ; i < n ; i ++ ) cin>>a[i];
for(int i = 0 ; i < n ; i ++ ){
f[i] = 1;
for(int j = 0 ; j < i ; j ++ )
if(a[i] > a[j]) f[i] = max(f[i], f[j] + 1);
}
for(int i = n-1 ; i >=0 ; i -- ){
g[i] = 1;
for(int j = n - 1 ; j > i ; j --){
if(a[i] > a[j]) g[i] = max(g[i] , g[j] + 1);
}
}
int ans = -1;
for(int i = 0 ; i < n ; i++ ){
ans = max(f[i] + g[i] - 1, ans);
}
cout<<n - ans<<endl;
return 0;
}
在相通之前我也思考了一下,为什么从中间到两段就可以呢
在中间点我们不妨设如下几种情况
1. 左边最高值大于最高值,不难发现,这种情况不成立。
2. 左边最高值小于右边最高值,同样的因为这个可以对称着看,也不成立。
3. 最后一种情况,左边的最高值 == 右边的最高值
我们假设如下一种情况
1 3 5 7 9 11 11 5 3 1
不难发现右边的 11 是可以去掉的,我们右边的最高值不妨取左边的 11 这样又与上述情况相同。
即我们不删除的数 = le(左) + len(右) - 1.
写这些什么意思呢,题目虽然很简单,但很多时候,题目很可能会存在特殊情况。
如果这些特殊情况不能好好的与通解兼容的话,就 WA 了。