题解：P3903 导弹拦截III

第一步：确定子任务

因为当前拦截的导弹可能在奇数位上，也可能在偶数位上，所以以这两种状态为子任务。

第二步：确定状态

设 $dp[i][0/1]$ 为作为第（偶数/奇数）个被拦截的导弹，最大可以拦截多少个导弹

第三步：推出转移方程

$dp[i][0]=max(dp[j][1])+1(1\le j< i且h[i]<h[j])$

$dp[i][1]=max(dp[j][0])+1(1\le j< i且h[i]>h[j])$

第四步：寻找边界条件

$dp[1][1]=1$

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,dp[1005][2],h[1005];
signed main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(ll i=1;i<=n;i++)cin>>h[i];
	dp[1][1]=1;
	for(ll i=2;i<=n;i++){
		for(ll j=1;j<i;j++)
			if(h[j]>h[i])dp[i][0]=max(dp[i][0],dp[j][1]+1);
		for(ll j=1;j<i;j++)
			if(h[j]<h[i])dp[i][1]=max(dp[i][1],dp[j][0]+1);
	}
	ll maxx=0;
	for(ll i=1;i<=n;i++)maxx=max(maxx,max(dp[i][0],dp[i][1]));
	cout<<maxx<<endl;
	return 0;
}