查看CodeVS/1044的源代码 ←CodeVS/1044

[[分类:序列动态规划‎]]
==摘要==
{{信息题|拦截导弹|http://www.codevs.cn/problem/1044/|2|100|算法错误|0|time=2014/10/16 20:00:24}}
==题意==
求最长不上升子序列长度 和 最少不上升子序列数。

（好像还不如原题说的明白-_-||）
==题解==
于是到了DP（动态规划）了，果然太久没写题了这么经典的一道题都写了很久。而且我深刻地检讨，只用了样例数据测试就交题的不良行为。

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

最长不上升子序列，就是对于第i项，采取的策略是：
*选取大等于自己的项接（必需条件）；
*能接上的中，其中选择最长的一个接上（最优条件1）；
*长度一定的时候，如果比原来的末尾项更大，就替换掉（最优条件2）。
于是循环下来就好了。两遍for解决是大约O（<m>n^2</m>）的（比如我写的）。LIS问题也可以用辅助数列二分查找解决，以后在[[CodeVS/1576]]中细说，这里就不多说了。

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

差不多就是酱紫。最后只能说太急着交题犯了一大堆错误，该打该打^_^
==代码==
{{折叠|1044.cpp代码已折叠
|<pre>#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;
}
</pre>
|code1044}}