題目大概:
一行數字要求從兩邊到中間依次增大,問給出的一行數字要去掉多少才能形成這種數列。
思路:
可以任選一個做中間數k,從1到n。
然後求第一個數到k的最長上升子序列的長度la,再求最後一個數到k的最長上升子序列的長度lb。
最後n-(la+la-1)就是去掉的數字個數,減一是因為多算了一個k。
感想:
有些題需要幾個簡單的算法混合使用或者重複使用。
代碼:
#include <iostream>
using namespace std;
int main()
{int n,thm=300;
int a[1001]={0},b[1001]={0},dp[1001]={0},c[1001]={0};
b[1]=1;
cin>>n;
for(int i=1;i<=n;i++)
{cin>>a[i];}
for(int y=1;y<=n;y++)
{int ma=0;
for(int i=2;i<=y;i++)
{
ma=0;
for(int t=1;t<i;t++)
{if(a[i]>a[t]){
if(b[t]>ma){ma=b[t];}
}
}
b[i]=ma+1;
}
c[n]=1;
for(int i=n-1;i>=y;i--)
{
ma=0;
for(int t=n;t>i;t--)
{if(a[i]>a[t]){
if(c[t]>ma){ma=c[t];}
}
}
c[i]=ma+1;
}
dp[y]=n-b[y]-c[y]+1;
if(thm>dp[y])thm=dp[y];
}
cout<<thm;
return 0;
}