贪心+动态规划LIS

LIS模型解决最多可以拦截多少颗炮弹+贪心 需要配置多少个系统，代码如下：

#include <bits/stdc++.h>
using namespace std;
int a[100001];
int v[100001];
int n=1;
int ans=0;//存储最少需要多少套系统 
int cnt=0;//拦截导弹数 
int dp[100001]; 
int main()
{
	while(cin>>a[n])
	{
		n++;
	}
	n--;
	int maxx=-99999;
    for(int i=1;i<=n;i++)
    {
        dp[i]=1;
        for(int j=1;j<i;j++)
            if(a[j]>=a[i])
            	dp[i]=max(dp[j]+1,dp[i]);
        
        maxx=max(maxx,dp[i]);
    }
    cout<<maxx<<endl;
	
	
	while(cnt<n)
	{
		ans++;
		int h=30000;
		for(int i=1;i<=n;++i)
		{
			if(a[i]<=h and v[i]==0)
			{
				cnt++;
				v[i]=1;
				h=a[i];
			}
		}	
	} 
	
	cout<<ans<<endl;
	
 return 0;
}