行业知识
超详细学习笔记:动态规划的时间优化(n*n -> n*logn)
luogu上刷到���P1020 [NOIP1999 提高组] 导弹拦截和P1439 【模板】最长公共子序列 有感
()LIS:Longest Increasing Subsequence,最长递增子序列
给定一个字符串,求出最长递减序列
这个题问的是下降,上升情况反过来就好了
()只考虑第一问,由于O(n*n)会爆T(不解释了),考虑压缩时间
还记得在网上看到的一句话
如果需要对dp进行时间优化,不妨交换状态参数和状态量
基于这句话的启发,这个题思路就若隐若现了
步骤一:首先我们很容易想到 dp[ i ] 来表示:前i个数中以第i个数结尾的最长递减序列
这句话中我理解的状态参数就是(以第i个数结尾)状态量就是(最长递减序列)
我们不妨构造 f 数组,f [ i ] 代表长度为 i 的递减序列的最后一个数的最大值
(为什么要怎么做,等会解释,先理解成最大值后面才能放更多小的数使序列更长)
这个时候状态参数就是(长度为 i 的递减序列)状态量就是(结尾的最大值)
这样我们就实现了递减序列和结尾数字的交换(前面可以再看一遍)
步骤二:需要一个前提证明,f 数组是单调递减的(其实是单调不递增,为了不拗口先这么叫):
反证一下,如果 f [x+1] > f [x] 也就是说长度为x+1的递减序列的末尾会大于长度为x的,那就不对了,由于序列递减,这个长度为x+1的序列的第x个数(称作a)一定>=第x+1个数(称作b),那长度为x的序列结尾的数至少就会跟这个a相等,也就是发 f [ x ] >=a,由于a>=b,b=f [ x+1 ],则 f [x] > f [x+1]得证。要是被绕了就看看这个例子:
长度为4的递减序列:9 6 3 2 ,如果长度为3的递减序列末尾比2还小就会冲突,因为这个序列至少可以取到9 6 3,这个最大值至少比3还大,也就不可能小于2了
步骤三:dp [ i ] 和 f [ i ] 同步进行计算,相互更新,计算dp[ i ] 需要对于每一个 i 满足:
想要用第i 个数结尾,前面的结尾必须比第i个数还大,但是前面满足的递减序列又要尽可能长,也就是i尽可能大,但是 f [ i ] 要比第i个数小,直接二分找到答案。(f 数组求dp数组)
每次计算完 dp [ i ] ,设这个长度为k, 也就是dp [ i ]=k,那么 f [ k ] 长度为k的递减序列的末尾就要尝试更新为第 i 个数。(dp 数组更新 f 数组)
最后遍历看看以谁结尾的最长递减序列最长就好了
AC代码如下(fun2函数是第二问的请忽略,后面的循环和ans数组也是):
//动态规划的时间优化 #include#define N 100050using namespace std;typedef long long ll;vectorans;ll h[N],dp[N],f[N];ll fun(ll i){ll l=0,r=N-1;while(l=h[i]){//等于的情况要特殊考虑!!! l=mid;}else{r=mid;}}if(f[r]>=h[i] && h[i]){return r;}else{return l;}}void fun2(ll i){if(ans.size()==0){ans.push_back(i);}else if(ans.size()==1){if(ans[0]>=i){ans[0]=i;}else{ans.push_back(i);}}else{ll l=0,r=ans.size()-1;while(li){r=mid;}else{l=mid;}}if(ans[l]>=i){ans[l]=i;}else if(ans[r]>=i){ans[r]=i;}else{ans.push_back(i);}}}int main(){ll n=1;while(cin>>h[n]){n++;}n--;dp[1]=1;f[1]=h[1];for(int i=2;i
上一篇:网易服务器怎么加组件?