泉州暑假集训Day 3

PS: This is a note.

动态规划(DP)

构成动态规划算法的三要素

动态规划对状态空间的遍历构成一张有向无环图，遍历顺序就是该有向无环图的一个拓扑序

• 有向无环图中的节点对应问题中的 “状态”
• 图中的边对应状态之间的 “转移”
• 转移的选取就是动态规划中的 “决策”

问题能用动态规划求解的三个基本条件

• 子问题重叠性————有些子问题会被重复计算多次，动态规划算法对每一个子问题只计算一次，然后将其计算结果保存下来，当再次需要计算已经计算过的子问题时，直接返回之前记录的结果，从而获得较高的效率
• 无后效性————动态规划要求已经求解的子问题不受后续阶段的影响，即每个状态都是过去历史的一个完整总结
• 最优子结构性质————问题的最优解,其所包含的子问题的解也是最优的

DP例题

e.g. 最少硬币找钱问题

e.g. 数字金子塔 II

e.g. 红牌(洛谷P1130)

e.g. 传球游戏(洛谷P1057)

e.g. 方格取数(洛谷P1004)

最长上升子序列(LIS)

LIS例题

e.g. 怪盗基德的滑翔翼(信息学奥赛一本通（C++版）在线评测系统 题号1286)

e.g. 登山(信息学奥赛一本通（C++版）在线评测系统 题号1283)

e.g. 友好城市(信息学奥赛一本通（C++版）在线评测系统 题号1263)

e.g. 最长上升子序列和(信息学奥赛一本通（C++版）在线评测系统 题号1285)

01背包

01背包公式: f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i])

#include<bits/stdc++.h>
using namespace std;
int f[2][1010],v[1010],w[1010];
int n,m,p;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i]>>w[i];
    }
    for(int i=1;i<=n;i++)
    {
        //动规方程
        
        for(int j=0;j<=m;j++)
        {
            f[1][j]=f[0][j];
            if(j>=v[i])
            {
                f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
            }
        }

        //优化(时间上无法优化，优化空间)

        p^=1;
        for(int j=0;j<=m;j++)
        {
            f[p][j]=f[p^1][j];
            if(j>=v[i])
            {
                f[p][j]=max(f[0][j],f[0][j-v[i]]+w[i]);
            }
        }
    }
    cout<<f[1][m]<<endl;
    cout<<f[p][m]<<endl;
}

完全背包