洛谷 P1020 拦截导弹

洛谷 P1020 拦截导弹

动态规划经典题

今天闲着无聊刷来刷洛谷上以前做过但是没有在洛谷提交的题目，忽然发现以前的基础确实很有必要温习。

首先，看下n^2 做法，n^2的动态规划很简单，核心代码是下面的getans 函数, 可以看到两问都用同一段代码完成了，f [ maxn ] 代表的是最长不上升子序列的长度，而dp [ i ]则是第二问的答案，是可以有定理证明的就是一个最长上升子序列，但是。。。我不会证，我惭愧得在我的题解里剽窃了结论。

n^2的方法

#include 
using namespace std;
const int maxn=1e6+7;
queue <int> Q;
int cnt=0,hi[maxn],k,dp[maxn],f[maxn],ans=1,ti=1;
void getans(){for(int i=2;i<=cnt;i++){for(int j=1;j<i;j++){if(hi[j] >= hi[i])f[i]=max(f[j]+1,f[i]);if(hi[j] < hi[i])dp[i]=max(dp[j]+1,dp[i]);}ans=max(ans,f[i]);ti=max(ti,dp[i]);}
}
int main(){while(~scanf("%d",&k)){hi[++cnt]=k;dp[cnt]=f[cnt]=1;}getans();printf("%d\n%d",ans,ti);
return 0;
}

nlogn方法：与n^2的方法不同，这里的dp和f数组，都是记录被选入的数字的，然后ans和ti就分别是这两个数组的长度。即答案。思想上就是保证在相同位置上的数字尽可能高，就是用二分查找 f 数组中第一个小于当前的数，然后替换，为什么可以替换呢。仔细想一想，就会发现，你把找到的位置的数字替换掉，不会对最长长度产生影响，所以结果是对的。

#include 
using namespace std;
const int maxn=1e6+7;
queue <int> Q;
int cnt=0,hi[maxn],k,dp[maxn],f[maxn],ans=1,ti=1;
void getans(){f[1]=dp[1]=hi[1];for(int i=2;i<=cnt;i++){if( f[ans] >= hi[i])f[++ans]=hi[i];else{int tmp=upper_bound(f+1,f+1+ans,hi[i],greater<int>())-f;//此处f[tmp]=hi[i];}if(dp[ti] < hi[i])dp[++ti]=hi[i];else{int tmp=lower_bound(dp+1,dp+1+ti,hi[i])-dp;dp[tmp]=hi[i];}}
}
int main(){memset(dp,0,sizeof(dp));memset(f,0,sizeof(f));while(~scanf("%d",&k)){hi[++cnt]=k;}getans();printf("%d\n%d",ans,ti);
return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！