动态规划 - 基础

盐盐

2023-10-29

动态规划 - 基础

reference

最长不下降子序列

可求子序列

$ \Theta(n^2)$

// 注：数组 a 从 1 开始
// dp[i] 表示末尾为下标 i 的子序列的长度
int a[N],dp[N],ans=-1e6,ansi;
int path[N],stack[N]; // 保存路径
dp[1]=1;
memset(path,0xFF,sizeof(path));
for(int i=2;i<=n;i++){
    dp[i]=1;
    for(int j=1;j<i;j++){
        if(a[i]>=a[j]){
            if(dp[j]+1>dp[i]){
                dp[i]=dp[j]+1;
                path[i]=j;
            }
            ans=max(ans,dp[i]),ansi=i
        }
    }
}
int top=-1;
stack[++top]=a[ansi];
while(path[ansi]!=-1) stack[++top]=a[path[ansi]],ansi=path[ansi];
while(top>=0) cout<<stack[top]<<" ",top--;

不可求子序列

$ \Theta(nlogn) $

// upper_bound(begin,end,num) 第一个大于 num 的数组项的指针
// lower_bound(begin,end,num) 第一个大于等于 num 的数组项的指针
// dp[i] 表示长度为 i 的子序列的末尾元素
int a[N],dp[N];
memset(dp, 0x1f, sizeof(dp));
mx=dp[0];
for (int i=1;i<=n;i++) {
  *upper_bound(dp+1,dp+n+1,a[i])=a[i];
}
ans=1;
while (dp[ans]!=mx) ++ans;
ans=ans-1;

那问题来了，当所求变为最长上升子序列，第二章方法该怎么改呢？
也好办，把 upper_bound() 变为 lower_bound() 就行了

原理

摘抄自 https://www.cnblogs.com/itlqs/p/5743114.html

考虑新进来一个元素a[i]：

如果这个元素大于等于d[len]，直接让d[len+1]=a[i]，然后len++。这个很好理解，当前最长的长度变成了len+1，而且d数组也添加了一个元素。

如果这个元素小于d[len]呢？说明它不能接在最后一个后面了。那我们就看一下它该接在谁后面。

准确的说，并不是接在谁后面。而是替换掉谁。因为它接在前面的谁后面都是没有意义的，再接也超不过最长的len，所以是替换掉别人。那么替换掉谁呢？就是替换掉那个最该被它替换的那个。也就是在d数组中第一个大于它的。第一个意味着前面的都小于等于它。假设第一个大于它的是d[j]，说明d[1…j-1]都小于等于它，那么它完全可以接上d[j-1]然后生成一个长度为j的不下降子序列，而且这个子序列比当前的d[j]这个子序列更有潜力（因为这个数比d[j]小）。所以就替换掉它就行了，也就是d[j]=a[i]。其实这个位置也是它唯一能够替换的位置（前面的替了不满足d[k]最小值的定义，后面替换了不满足不下降序列）

至于第一个大于它的怎么找……STL upper_bound。每次复杂度logn。