题目大概: 一行数字要求从两边到中间依次增大,问给出的一行数字要去掉多少才能形成这种数列。 思路: 可以任选一个做中间数k,从1到n。 然后求第一个数到k的最长上升子序列的
题目大概:
一行数字要求从两边到中间依次增大,问给出的一行数字要去掉多少才能形成这种数列。
思路:
可以任选一个做中间数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;
}