（以“分类:序列动态规划 ==摘要== {{信息题|拦截导弹|http://www.codevs.cn/problem/1044/|2|100|算法错误|0|time=2014/10/16 20:00:24}} ==题意== ...”为内容创建页面） |
小 （去除并列最长公共子序列LCS的说法） |
||
| 第15行： | 第15行： | ||
*能接上的中，其中选择最长的一个接上（最优条件1）； | *能接上的中，其中选择最长的一个接上（最优条件1）； | ||
*长度一定的时候，如果比原来的末尾项更大，就替换掉（最优条件2）。 | *长度一定的时候，如果比原来的末尾项更大，就替换掉（最优条件2）。 | ||
| − | 于是循环下来就好了。两遍for解决是大约O（<m>n^2</m> | + | 于是循环下来就好了。两遍for解决是大约O（<m>n^2</m>）的（比如我写的）。LIS问题也可以用辅助数列二分查找解决，以后在[[CodeVS/1576]]中细说，这里就不多说了。 |
然后第二小题，就是扫一遍看一下有没有能塞进去的子序列，能的话就塞进去，塞不进去就新建一个。为了保证最优，在能塞进去的里面一定要选一个末项最小的塞进去。 | 然后第二小题，就是扫一遍看一下有没有能塞进去的子序列，能的话就塞进去，塞不进去就新建一个。为了保证最优，在能塞进去的里面一定要选一个末项最小的塞进去。 | ||
| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 失误原因（初次提交分数） |
|---|---|---|---|---|---|
| 拦截导弹 | ★★☆☆☆ | 答案正确 | 100 | 2014/10/16 20:00:24 | 算法错误（0） |
求最长不上升子序列长度 和 最少不上升子序列数。
（好像还不如原题说的明白-_-||）
于是到了DP（动态规划）了，果然太久没写题了这么经典的一道题都写了很久。而且我深刻地检讨，只用了样例数据测试就交题的不良行为。
其实完全就是两个小题辣。
最长不上升子序列，就是对于第i项，采取的策略是：
于是循环下来就好了。两遍for解决是大约O（）的（比如我写的）。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;
}
|
CloudLunar