Initiate

Call A Spade a Spade
posts - 14, comments - 3, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

POJ3700 Missile Defence System

Posted on 2010-04-05 16:26 Initiate 阅读(790) 评论(0)  编辑 收藏 引用 所属分类: 贪心搜索
对于一套导弹拦截系统,它要不可以拦截上升序列,要不可以拦截下降序列,现在问最少需要多少套系统。
很自然的想到LIS算法,可惜在这里不能用,如果这样贪心的话
每套系统拦截最多的导弹和系统的数量最少没有什么直接联系,应该不会正确

而LIS中,最核心的思想在于能否将一个元素加入到序列中,只与这个序列目前的最后一个元素有关
这道题就用了这个关键的思想。
用up[k]和down[k]记录第k套上升(下降)系统目前所拦截的最后一个导弹
dfs(u,v,t)意味着已有u个上升,v个下降,正在处理第t个数

按理说,每拿到一个新的数字应该将它所有能放入的序列都放一遍的
但扩展节点时却存在一个贪心策略,大大节省了时间。
假设现在要把一个数放入一个上升序列,那么一定是所有能放入的上升序列中,最后一个元素最大的那一个。
其实想想也是,既然每个数字都要放到一个序列中,
对于上升序列,肯定是目前越小越有用,既然能放入大的里面,何必浪费一个小的呢
注意到其实up[i]按这种策略已经是排好序的了,所以只用找最先碰到的一个就行了

这样将深搜的树从一个多叉树变成了二叉树,时间效率提升很大。

#include<iostream>
using namespace std;
#define max(a,b) a>b?a:b
int n,res,a[60];
int up[60],down[60];
void dfs(int u,int v,int t) 
{
    
if(u+v>=res)return;
    
if(t>n)
    {
        
if(u+v<res)res=u+v;
        
return;
    }
//找到更好的结果
    int i,tmp;
    
//UP
    for(i=1;i<=u;i++)
        
if(up[i]<a[t]) break;
    tmp
=up[i];
    up[i]
=a[t];
    dfs(max(i,u),v,t
+1);
    up[i]
=tmp;
    
//DOWN
    for(i=1;i<=v;i++)
        
if(down[i]>a[t]) break;
    tmp
=down[i];
    down[i]
=a[t];
    dfs(u,max(i,v),t
+1);
    down[i]
=tmp;
}
int main()
{
    
int i;
    
while(scanf("%d",&n) && n)
    {
        res
=100;
        
for(i=1;i<=n;i++)
            scanf(
"%d",&a[i]);
        dfs(
0,0,1);
        printf(
"%d\n",res);
    }
}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理