导弹防御系统 ACwing187 最长上升/下降子序列+贪心+DFS-白红宇的个人博客

导弹防御系统 ACwing187 最长上升/下降子序列+贪心+DFS

发布日期：2021-05-10 11:28:56 浏览次数：21 分类：精选文章

本文共 782 字，大约阅读时间需要 2 分钟。

题目链接

题意

导弹只能打掉严格递增或者严格递减的一段序列，求覆盖n个目标需要多少导弹

思路

如果只看严格递增或者严格递减就是导弹拦截的贪心做法，因为有严格递增或者严格递减的限制，所以在外面套一个搜索的壳就行了，注意维护全局变量ans，以便剪枝

代码

#include
   
    #include
    
     #include
     
      #include
      #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
               #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define endl "\n"//#define int long long//#define double long doubleusing namespace std; typedef long long ll; const int maxn=55; const int inf=0x3f3f3f3f; int n,m; int a[maxn]; int d1[maxn],d2[maxn]; int ans; void dfs(int now,int up,int down){ if(up+down>=ans) return ; if(now==n+1){ ans=up+down; return ; } int k=0; while(k
              
               =a[now]) k++; int t=d1[k]; d1[k]=a[now]; if(k
               
                >n,n){ ans=n; for(int i=1;i<=n;i++) cin>>a[i]; dfs(1,0,0); cout<
                
                 <

上一篇：CodeForces - 1443D Extreme Subtraction 差分应用

下一篇：导弹拦截 NOIP1999 dilworth定理裸题

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

题目链接

题意

思路

代码

发表评论

最新留言

关于作者

推荐文章