动态规划及其优化

· · 算法·理论

T_0 方格取数

有一个 N\times M 的网格，第 i 行第 j 列的格子里有一个整数 A_{i,j}。

有一只小熊想从网格的左上角走到右下角。每一步只能：

移动一格，不能重复经过已走过的方格，也不能越界。\ 小熊会收集所有经过方格中的整数，求这些整数的最大可能和。

限制条件

定义

### 转移 从第 $j-1$ 行的某个格子 $(i',j-1)$ 先向右走一步然后再向上或向下走到 $(i,j)$ 上。 分两步求解一列的 $f_{[i][j]}$： 1. 从上向下 2. 从下向上 ### 代码 ```cpp #include<bits/stdc++.h> using namespace std; #define var long long #define ln "\n" /*Optimization series #pragma GCC/G++ optimize(1) #pragma GCC/G++ optimize(2) #pragma GCC/G++ optimize(3,"Ofast","inline") */ struct Node{ var data; var up; var down; var right; }; Node a[1100][1100]; var n,m; int main(){ freopen("number.in","r",stdin); freopen("number.out","w",stdout); ios::sync_with_stdio(); cin.tie(); cout.tie(); cin>>n>>m; for(var i=1;i<=n;i++){ for(var j=1;j<=m;j++){ cin>>a[i][j].data; } } for(var i=1;i<=n;i++){ if(i==1) a[i][1].right=a[i][1].down=a[i][1].data; else a[i][1].right=a[i][1].down=a[i-1][1].down+a[i][1].data; } for(var i=2;i<=m;i++){ for(var j=1;j<=n;j++){ if(j==1) a[j][i].down=a[j][i-1].right+a[j][i].data; else a[j][i].down=max(a[j][i-1].right,a[j-1][i].down)+a[j][i].data; } for(var j=n;j>=1;j--){ if(j==n) a[j][i].up=a[j][i-1].right+a[j][i].data; else a[j][i].up=max(a[j][i-1].right,a[j+1][i].up)+a[j][i].data; } for(var j=1;j<=n;j++){ a[j][i].right=max(a[j][i].up,a[j][i].down); } } cout<<a[n][m].right<<endl; return 0; } ``` ## $T_1$ 方格取数 ### 题意 有一个 $N\times M$ 的网格，第 $i$ 行第 $j$ 列的格子里有一个整数 $A_{i,j} $。 有一只小熊想从网格的左上角走到右下角。每一步只能： - 向上 - 向下 - 向右 移动一格，能重复经过已走过的方格，但重复走不会获得更多的得分，也不能越界。 小熊会收集所有经过方格中的整数，求这些整数的**最大可能和**。 ## 限制条件 - $1\leq N,M\leq 10^{3}

定义

$g1_{[i]}$ 为第 $i$ 行的从前向后的最大子段和。 $g2_{[i]}$ 为第 $i$ 行的从后向前的最大子段和。 ### 转移 $$f_{[i][j]}=\max_{k=1}^{n}\left\{ f_{[k][j-1]}+\sum_{p=i}^{k}{a_{[p][k]}}+g2_{[k+1][j-1]}+g1_{[i-1][j-1]} \right\}$$ ### 优化 考虑前缀和。 $$sum_{[i][j]}=sum_{[i-1][j]}+a_{[i]}$$ 此时： $$sum_{[i][j]}-sum_{[i][k-1]}=\sum_{p=k}^{j}{a_{[i][p]}}$$ ### 新的转移方程 $$f[i][j]=\max_{k=1}^{n}\left\{ f_{[k][j-1]}+sum_{[k][k]}-sum_{[i-1][k]}+g2_{[k+1][j-1]}+g1_{[i-1][j-1]} \right\}$$ ## $T_2$ 接龙 ### 题意 在玩惯了成语接龙之后，小 J 和他的朋友们发明了一个新的接龙规则。 总共有 $n$ 个人参与这个接龙游戏，第 $i$ 个人会获得一个整数序列 $S_i$ 作为他的词库。 一次游戏分为若干轮，每一轮规则如下： - $n$ 个人中的某个人 $p$ 带着他的词库 $S_p$ 进行接龙。若这不是游戏的第一轮，那么这一轮进行接龙的人不能与上一轮相同，但可以与上上轮或更往前的轮相同。 - 接龙的人选择一个长度在 $[2, k]$ 的 $S_p$ 的连续子序列 $A$ 作为这一轮的 **接龙序列**，其中 $k$ 是给定的常数。若这是游戏的第一轮，那么 $A$ 需要以元素 $1$ 开头，否则 $A$ 需要以上一轮的接龙序列的最后一个元素开头。 - 序列 $A$ 是序列 $S$ 的连续子序列当且仅当可以通过删除 $S$ 的开头和结尾的若干元素（可以不删除）得到 $A$。 为了强调合作，小 J 给了 $n$ 个参与游戏的人 $q$ 个任务，第 $j$ 个任务需要这 $n$ 个人进行一次游戏，在这次游戏里进行恰好 $r_j$ 轮接龙，且最后一轮的接龙序列的最后一个元素恰好为 $c_j$。为了保证任务的可行性，小 J 请来你判断这 $q$ 个任务是否可以完成的，即是否存在一个可能的游戏过程满足任务条件。 ### 定义 $f_{[i][j][k]}$ 为第 $i$ 轮接龙，以 $j$ 结尾，当前接龙人数为 $k$。 ### 观察 + 我们发现只在意上一个接龙者是否为自身，于是我们可以将其优化成一个 `0-1` 型的动态规划。 + 若存在 $f_{[i][j][k_1]}=1$ 且 $f_{[i][j][k_2]}=1$，并且同时满足 $k_1 \not= k_2$，我们发现第三维是可以优化掉的。 ### 重新定义 $f_{[i][j]}$ 为第 $i$ 轮接龙，以 $j$ 结尾。 $$ f_{[i][j]}= \left\{\begin{matrix} -1 & \text{没人}\\ 0 & \ge 2 \text{个人}\\ k & \text{只有} k \text{个人可以接龙} \end{matrix}\right. $$ ### 时间复杂度 如果我们算出每一个 $f_{[i][j]}$。 就能在 $O(1)$ 的时间复杂度内回答每个问题。 假设在第 $i$ 轮派第 $p$ 个人上场，并选择子串 $S_{p}[l..r]$ 作为接龙序列，则考虑以下状态转移： 从状态 $(i-1,j)$（其中 $j \in S_{p}[l..r-1]$）转移到状态 $(i,S_{p}[r])$。 当满足以下任一条件时： - $f[i-1][j] = 0

则状态 (i,j) 是可达到的，且最后一轮上场人员可以设为p。

符号说明

代码

#include <bits/stdc++.h>
using namespace std;
#define var long long
#define ln "\n"
/*Optimization series
#pragma GCC/G++ optimize(1)
#pragma GCC/G++ optimize(2)
#pragma GCC/G++ optimize(3,"Ofast","inline")
*/

const var MaxN=2e5+10;
var n,k,q,dp[110][MaxN];
vector<var> v[MaxN];

void solve(){
    memset(dp,-1,sizeof dp);
    cin>>n>>k>>q;
    for(var i=1;i<=n;i++){
        var l;
        cin>>l;
        v[i].clear();
        for(var j=0,x;j<l;j++){
            cin>>x;
            v[i].push_back(x);
        }
    }

    dp[0][1]=0;
    for(var r=1;r<=100;r++){
        for(var i=1;i<=n;i++){
            var cnt=0;
            for(auto u:v[i]){
                if(cnt>0){
                    if(dp[r][u]==-1) dp[r][u]=i;
                    else if(dp[r][u]!=i) dp[r][u]=0;
                    cnt--;
                }

                if(dp[r-1][u]!=-1 && dp[r-1][u]!=i){
                    cnt=k-1;
                }
            }
        }
    }

    while(q--){
        var r,c; 
        cin>>r>>c;
        cout<<((dp[r][c]==-1)?0:1)<<ln;
    }
}

int main(){
    ios::sync_with_stdio();
    cin.tie();
    cout.tie();

    var T;
    cin>>T;
    while(T--){
        solve(); 
    }
    return 0;
}

T_3 多重背包

题意

有一个容量（即承重量）为 M 克的背包。有N种物品，从1到N编号，第i种物品有 C_i 个。一个第i种物品的重量是W_i克，价值是V_i元。

要求选择一些物品放入背包，所选物品的重量之和不能超过背包的容量。

求所选物品的总价值可能达到的最大值。

做法

思路一

将多重背包转化为 \sum_{i=1}^{N}{C_i} 个 0-1 背包。 时间复杂度 O(M \sum_{i=1}^{N}{C_i})。

思路二

发现在思路一中采用二进制优化。

物品分组优化方法

将每种物品分成若干组，选择物品时以组为单位而非单个物品。通过合理的分组设计，使得1到C_i之间的任意数量都能由这些组的组合表示。

对于任意 C_i 个物品，应满足：

  1. 分组数量尽可能少
  2. 通过组间组合能表示 1 到 C_i 的所有整数
  3. 典型分组方式：按 2^k 序列分组（1, 2, 4, 8,\dots）

设物品 i 的总数为 C_i，将其拆分为：

\left\{ 2^0, 2^1,...,2^{k-1},C_i-2^k+1 \right\}

其中 k 满足 2^{k+1}-1 \geq C_i。 时间复杂度 O(N M \log_{2}{\max_{i=1}^{N}{C_i}})。

思路三

定义

令 f[i][j] 表示：

初始问题的解即为 f[N][M]，其中：

  1. 二维状态表示：同时记录物品选择范围和容量限制
  2. 最优子结构：当前状态由前序状态转移得到
  3. 最终解定位：解存储在状态矩阵的右下角（f[N][M]）
    转移

    枚举从第 i 种物品中拿几个：

    f[i][j_{k}]=\max _{0\leq p\leq\min\left(k, C_{i}\right)} f[i-1]\left[j_{k-p}\right]+p\cdot V_{i}

    我们发现所有 j-pW_N \bmod{W_i} 均相等。 把

    f[i][j_{k}]=\max _{0\leq p\leq\min\left(k, C_{i}\right)} f[i-1]\left[j_{k-p}\right]+p\cdot V_{i}

    改写成

    f[i][j_{k}]=k\cdot V_{i}+\max _{0\leq p\leq\min\left(k, C_{i}\right)} \left(f[i-1]\left[j_{k-p}\right]-(k-p)\cdot V_{i}\right)

    把 f[i-1]\left[j_{k-p}\right]-(k-p)\cdot V_{i} 记作 A_{i}[k-p]，上式变成

    f[i][j_{k}]=k\cdot V_{i}+\max _{0\leq p\leq\min\left(k, C_{i}\right)} A_{i}[k-p]

    令 t = k - p，将上式改写为：

    f[i][j_{k}]=k\cdot V_{i}+\operatorname*{max}_{\max(0,k-C_{i})\leq t\leq k}A_{i}[t]

    计算 f[i][j_k] 转化为计算：

    \max _{\max (0,k-C_{i})\leq t\leq k}A_{i}[t]

计算 f[i][j_{k+1}] 转化为计算：

\max _{\max (0,k+1-C_{i})\leq t\leq k+1}A_{i}[t]

通过对比可见：