| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 失误原因（初次提交分数） |
|---|---|---|---|---|---|
| 拦截导弹 | ★★☆☆☆ | 答案正确 | 100 | 2014/10/16 20:00:24 | 算法错误（0） |
求最长不上升子序列长度 和 最少不上升子序列数。
（好像还不如原题说的明白-_-||）
于是到了DP（动态规划）了，果然太久没写题了这么经典的一道题都写了很久。而且我深刻地检讨，只用了样例数据测试就交题的不良行为。
其实完全就是两个小题辣。
最长不上升子序列，就是对于第i项，采取的策略是：
于是循环下来就好了。两遍for解决是大约O（）的（比如我写的）。LIS/LCS问题也可以用辅助数列二分查找解决，以后在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