题目描述
花匠栋栋种了一排花，每株花都有自己的高度。花儿越长越大，也越来越挤。栋栋决定把这排中的一部分花移走，将剩下的留在原地，使得剩下的花能有空间长大，同时，栋栋希望剩下的花排列得比较别致。
具体而言，栋栋的花的高度可以看成一列整数h,h...h。设当一部分花被移走后，剩下的花的高度依次为g,g...g，则栋栋希望下面两个条件中至少有一个满足：
注意上面两个条件在m=1时同时满足，当m>1时最多有一个能满足。
请问，栋栋最多能将多少株花留在原地。
思路
（这种算法很慢，而且比起贪心可能更难理解。但是在dp中算是最直接的一种办法
首先看到这题很容易想到LIS（最长上升子序列）
于是开两个数组表示条件a和条件b，一个整数i表示到第i个数的最大长度，并用0或1来表示接下来要选更大的还是更小的。
然后就……就TLE了。代码：
#include<iostream> using namespace std; int a[],fa[][],fb[][],n; int main()
{
cin>>n;
for(int i=;i<=n;i++)
cin>>a[i];
fa[][]=fb[][]=fa[][]=fb[][]=;
for(register int i=;i<=n;i++)
{
for(register int j=;j<i;j++)
{
if(a[j]<a[i])
{
fb[i][]=max(fb[i][],fb[j][]+);
fa[i][]=max(fa[i][],fa[j][]+);
}
if(a[j]>a[i])
{
fb[i][]=max(fb[i][],fb[j][]+);
fa[i][]=max(fa[i][],fa[j][]+);
}
}
}
cout<<max(fb[n][],max(fa[n][],max(fb[n][],fa[n][])));
return ;
}
但是这题不像LIS，它只需要上一个数比他小（大）就行了，只要在前面找到一个比他小的数，那就肯定表明这个数之前的序列都更短。
所以每次从后往前搜，能转移就转移。更大和更小都转移完了之后，就能够从中选取答案了。
代码：
#include<iostream>
using namespace std; int a[],fa[][],fb[][],n;
bool flag1,flag2; int main()
{
cin>>n;
for(int i=;i<=n;i++)
cin>>a[i];
fa[][]=fb[][]=fa[][]=fb[][]=;
for(register int i=;i<=n;i++)
{
flag1=flag2=;
for(register int j=i;j>=&&(flag1||flag2);j--)
{
if(a[j]<a[i])
{
flag1=;
fb[i][]=max(fb[i][],fb[j][]+);
fa[i][]=max(fa[i][],fa[j][]+);
}
if(a[j]>a[i])
{
flag2=;
fb[i][]=max(fb[i][],fb[j][]+);
fa[i][]=max(fa[i][],fa[j][]+);
}
}
}
cout<<max(fb[n][],max(fa[n][],max(fb[n][],fa[n][])));
return ;
}