摘要

题目链接 难度等级 完成状态 完成分数 最后编辑时间 失误原因(初次提交分数)
拦截导弹 ★★☆☆☆ 答案正确 100 2014/10/16 20:00:24 算法错误(0)

题意

求最长不上升子序列长度 和 最少不上升子序列数。

(好像还不如原题说的明白-_-||)

题解

于是到了DP(动态规划)了,果然太久没写题了这么经典的一道题都写了很久。而且我深刻地检讨,只用了样例数据测试就交题的不良行为。

其实完全就是两个小题辣。

最长不上升子序列,就是对于第i项,采取的策略是:

  • 选取大等于自己的项接(必需条件);
  • 能接上的中,其中选择最长的一个接上(最优条件1);
  • 长度一定的时候,如果比原来的末尾项更大,就替换掉(最优条件2)。

于是循环下来就好了。两遍for解决是大约O(n^2)的(比如我写的)。LIS问题也可以用辅助数列二分查找解决,以后在CodeVS/1576中细说,这里就不多说了。

然后第二小题,就是扫一遍看一下有没有能塞进去的子序列,能的话就塞进去,塞不进去就新建一个。为了保证最优,在能塞进去的里面一定要选一个末项最小的塞进去。

差不多就是酱紫。最后只能说太急着交题犯了一大堆错误,该打该打^_^

代码

1044.cpp代码已折叠
展开折叠内容
#include<iostream>
int height[51]={},n=0;
const int maxLength()
{
    int maxLength=0,f[51]={50000};
    for(int i=1;i<=n;++i)
    {
        for(int j=maxLength+1;j>=1;--j)
        {
            if(height[i]<=f[j-1]&&height[i]>=f[j])
            {
                f[j]=height[i];
                maxLength=std::max(j,maxLength);//Fixed01:原本未取max 
            }
        }
    }
    return maxLength;
}
const int requiredSys()
{
    int sysNum=0,sysHeight[51]={};
    for(int i=1;i<=n;++i)
    {
        int chosenSys=0,chosenSysHeight=50000;
        for(int j=1;j<=sysNum;++j){
            if(height[i]<=sysHeight[j]&&chosenSysHeight>=height[i])
            {
                chosenSys=j;
                chosenSysHeight=height[i];
            }
        }
        if(!chosenSys)
        {
            sysHeight[++sysNum]=height[i];
        }
        else//Fixed03:成功拦截的未记录 
        {
            sysHeight[chosenSys]=height[i];
        }
    }
    return sysNum;
}
int main()
{
    while(std::cin>>height[++n]);//Fixed02:n++ -> ++n
    --n;
    std::cout<<maxLength()<<std::endl<<requiredSys()<<std::endl;
}

著作权声明[编辑]

关于[编辑]