基础动态规划 —— ylxmf2005的OI教程

思考步骤

  1. 看出是动态规划

  2. 顺着想倒着退 通过数据范围与题目判断状态的维度与转移复杂度

  3. 设计状态

  4. 考虑初始值 边界

  5. 设计状态转移 检查是否具有最优子结构 无后效性等


最长路问题

简介

题目中出现了最长两字,数据间的关系是定向的 闭上眼睛深吸一口气 ,凭直觉感到这就是或不是$DAG$最长路,经常需要预处理。

$DAG$即为有向无环图,$DAG$最长路是动态规划的一类经典问题。

$DAG$图求最长路径,拓扑序的基础上进行$dp$即可。

拓扑排序的步骤:每次选取一个入度为$0$的点,将其和它所连的边"删除",重复下去直到图为空。然后删除的顺序就是拓扑序。

当然也可以记忆化搜索。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
queue<int>q;
vector<int>E[N];
int n,m,ans;
int dp[N],indegree[N];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) 
    {
        int x,y;
        scanf("%d%d",&x,&y);
        E[x].push_back(y); 
        indegree[y]++;
    }
    for(int i=1;i<=n;i++) 
        if(!indegree[i]) 
            q.push(i);
    while(!q.empty()) 
    {
        int u=q.front(); 
        q.pop();
        for(int i=0;i<E[u].size();i++) 
        {
            int uu=E[u][i];
            indegree[uu]--;
            if(!indegree[uu]) 
            {
                dp[uu]=dp[u]+1;
                q.push(uu);
            }
        }
    }
    int maxn=0;
    for(int i=1;i<=n;i++) 
        maxn=max(maxn,dp[i]);
    printf("%d\n", maxn);
    return 0;
}

最长单调子序列

简介

没有预处理,最长单调子序列有何用途?题目让你看不出是最长单调子序列才是最大的成功!

下面默认再讲最长不下降子序列

由于$O(n^2)$太简单,直接说$O(nlogn)$的算法。

假设当前的序列已经是不下降序列,当我们添加一个数的时候,我们要考虑这个数的位置,显然最理想的位置是序列的最后面。如果这个数不能添加到序列怎么办?按照直觉,如果我们用一个小的数替换掉一个大的数,那么就可以容纳进更多的数,因此可以从头找到第一个大于它的数并且替换。由于当前序列已经是单调序列,所以这个过程可以用二分实现。

网上几乎全部人认为$O(nlogn)$的算法不能储存答案,实际上$O(nlogn)$计算储存答案是可以的。

需要增加一个$c$数组 用来记录每个元素在最长序列中的位置。输出时,从 数组$a$的尾部开始,逆序依次找出 $c$ 为 $p, p-1, p-2 … 3, 2,1$的元素,并且找到一个就接着寻找 $c_i-1$,直到找到 $c_i$ 为 $1$的数。储存下来倒序输出即可。最长上升子序列需要将二分那的$upperbound( )$改为$lowerbound( )$。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
int dp[MAXN],a[MAXN],c[MAXN];  
int main()
{
    int n; scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    if(!n)
    {
        puts("0");
        return 0;
    }
    dp[1]=a[1];
    int p=1;
    for(int i=2;i<=n;i++)
    {
        if(a[i]>=dp[p]) 
        {
            dp[++p]=a[i];
            c[i]=p;
        }
        else 
        {
            int j=upper_bound(dp+1,dp+p+1,a[i])-dp;
            dp[j]=a[i]; c[i]=j;
        }
    }
    stack<int>ans;
    for(int i=n,j=p;i>=1;i--)
    {
        if(c[i]==j)
        {
            ans.push(a[i]);
            j--;    
        } 
        if(j==0)
            break;
    }
    printf("%d\n",p);
    while(!ans.empty())
    {
        printf("%d ",ans.top());
        ans.pop();
    }
    return 0;
} 

杨辉三角

杨辉三角是什么?重要吗?难道不是数论吗?为什么放在动态规划将讲?

因为本人认为,杨辉三角与许多动归题目有着联系,甚至许多题目用到了杨辉三角的思想

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

这就是杨辉三角,不难发现,杨辉三角的斜边与第一列全都是$1$,其余每一项都等于上面两项的和。

即为$C(n,m)=C(n-1,m-1)+C(n-1,m)$。其实这就是组合数的公式,所以我们利用杨辉三角可以再$O(n^2)$中打出组合数的表,非常适用于一些$n,m$很小,询问次数很多的数学题目。

当然这不是重点,重点是组合数的这个公式是怎么得到的。

显然我们在$n$个物品中选$m$个,最后一个可以选或不选,如果选的话,就用在前$n-1$个物品中选$m-1$个,否则就要在前$n-1$个物品中选$m$个。这就是动态规划的一个常用技巧。


for (int i=0;i<n;i++)
    a[i][0]=1;
for (int i=0;i<n;i++)
    a[i][i]=1;
for (int i=1;i<n;i++)
{
    for (int j=1;j<i;j++)
        a[i][j]=a[i-1][j-1]+a[i-1][j];
}

背包问题

背包是动态规划的精髓。

设$dp_i$表示选重量不大于$i$的货品的最大价值,则 $dp_i=max( dpi,dp{i–w_j}+v_j)$ .

for (int i = 1; i <= n; i++)
        for (int j = w[i]; j <= m; j++)
                dp[j] = max (dp[j], dp[j - w[i]] + v[i]);

01背包

下面会重点讲解$01$背包

设$dp_{i,j}$为在前$i$个货品中选择重量不大于$j$的货品的最大价值。那么每种物品有两种情况选或不选,这个就与上面杨辉三角很相似了。但是二维的空间有时会炸,那么我们需要优化一下,滚动数组当然可以,但是有的时候还会炸,那么介绍一下一维的做法:

一维的做法还是基于滚动数组的,那么我们要把二维的滚动数组变成一维的。

我们看看在二维情况下的转移方法,是从蓝色转移到红色:

《基础动态规划 —— ylxmf2005的OI教程》

不难想到把蓝色和红色挤成一列,但是有的时候不会满足每个物品只能用一次的条件,怎么办?重点:

容量大的时候的值取决于容量小的时候的值,如果我们倒着枚举价值,那么当前枚举到大的价值取决于前面小的价值,前面小的价值可能是$0$,也可能是上一次算出的最优解,这样就可以了。那么为什么正着枚举不行?因为正着枚举先更新小的价值,大的价值会受到小的价值的影响!

cin >> n >> m;
for (int i = 1; i <= n; i++)
{
    cin >> w >> v;
    for (int j = m; j >= w; j--)
            dp[j] = max (dp[j - w] + v, dp[j]); 
} 
cout << dp[m] << endl;

多重背包

利用转换的思想,把多个相同的物品视为同一种物品,这样不就是变成$01$背包了吗?但是复杂度咕咕。

© ylxmf2005
All rights reserved.
本文不遵从 CC BY-SA 4.0 协议,转载请联系作者。

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据