本文主要是介绍NYoj 79 导弹拦截[典型动态规划1]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
/*NYoj 79 导弹拦截典型的动态规划问题.(列为典型动态规划1)时间复杂度为O（n^2）
*/
#include<iostream>
#include<memory.h>
#define max(a,b) a>b?a:b
using namespace std;
int main()
{int T;cin>>T;while(T--){int n,a[25],dp[25],Max=0;cin>>n;for(int i=1;i<=n;i++) dp[i]=1;//初始化为1的原因是，每一个导弹都可以作为起始导弹.for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){for(int j=i;j>=1;j--)if(a[j]>a[i])dp[i]=max(dp[i],dp[j]+1);//dp[i]存储的是当前导弹可以拦截的最优解.Max=max(Max,dp[i]);}cout<<Max<<endl;}
}
这篇关于NYoj 79 导弹拦截[典型动态规划1]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
