dp总结

最近发现之前学过的很多dp优化都忘了==所以写篇文章复习一下,以备查找。

最长上升子序列(LIS)

dp方程

$d[i]=max{d[k]+1}(k<i,a[k]<a[i])$
复杂度$O(n^2)$

优化

因为$d$值相同时只需保留最小的$a$值,所以令$g[i]$为$d[k]==i$中$k$的最小值，显然$g[1]\leq g[2]\leq \cdots \leq g[k]$
那么计算$d[i]$时，只需在$g$中找到最小的$k$使$g[k]\ge a[i]$，则$d[i]=k$，此时，$a[i]\le g[k]$，所以更新$g[k]=a[i]$
STL中的lower_bound函数可以在$O(logn)$的时间内找到第一个大于等于k的数，因此复杂度可以优化到$O(nlogn)$
代码如下:

memset(g,0x3f,sizeof(g));
for(register int i=1;i<=n;i++)
{
    int j=lower_bound(g+1,g+n+1,a[i])-g;
    d[i]=j;
    g[j]=a[i];
}

循环部分甚至可以简写成:

for(register int i=1;i<=n;i++)d[i]=lower_bound(g+1,g+n+1,a[i])-g,g[d[i]=a[i];

应用

二维偏序分组(dilworth+lis:导弹拦截)，LCS(其中一组映射成有序数列，另一组求最长上升子序列)等。

咕咕咕