3903 导弹拦截Ⅲ
又是导弹拦截
嘿嘿嘿
马上就要去金乡了,好开心啊
做完这一道题,就结束了,我去学文化课了,洛谷上的搜索到此结束,开始杀向一本通
ok了,切入正题
嗯?貌似这个题需要跑两个最长不下降子序列?纯属猜测
这个题就是在上一个导弹拦截的基础上,求一连串最长序列,可是这条序列的第奇数个要比前一个高,偶数的一个比一个个短
那么,我们就可以分奇数偶数位置来,也就是说,如果是第奇数个,我们就找前一个的最长的偶数;如果是第偶数个,我们就找前面一个的奇数
if(a[j]<a[i]) dp[i][1]=max(dp[i][1],dp[j][0]+1);//奇数
if(a[j]>a[i]) dp[i][0]=max(dp[i][0],dp[j][1]+1);//偶数
但是对于每一个导弹,我们都可以对其进行拦截或者不拦截,每一个导弹都可以成为拦截的导弹
所以我们还得初始化f[i][1]=1表示都会很成为第一颗拦截的导弹
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,ans;
int a[1005],f[1005][5];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
f[1][1]=1;//边界
for(int i=2;i<=n;i++)
{
f[i][1]=1;//第二维度表示奇数或者偶数位置
for(int j=1;j<=i-1;j++)
{
if(a[j]<a[i]) f[i][1]=max(f[i][1],f[j][0]+1);//如果下降就是奇数
if(a[j]>a[i]) f[i][0]=max(f[i][0],f[j][1]+1);//如果上升就是偶数
}
ans=max(ans,max(f[i][1],f[i][0]));
}
cout<<ans<<endl;
return 0;
}