动态规划分类选题

2021-03-14 | 阅读：次

===

Index

树形DP
换根dp
状态压缩dp
- 完成所有工作的最短时间
- 完成任务的最少工作时间段
线段树优化dp
- 最小可能后缀和
- 数组最长分段和
环形/区间动态规划
- 环上相邻位置数字不同的方案数
- 得到理想队列的原始排列方案数
计数dp
- n乘2数组填充方案数

树形dp

没有上司的舞会

acwing 285

Ural 大学有 N 名职员，编号为 1∼N。他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。每个职员有一个快乐指数，用整数 Hi 给出，其中 1≤i≤N。现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。

在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。

输入格式 第一行一个整数 N。

接下来 N 行，第 i 行表示 i 号职员的快乐指数 Hi。

接下来 N−1 行，每行输入一对整数 L,K，表示 K 是 L 的直接上司。

输出格式 输出最大的快乐指数。

数据范围 1 ≤ N ≤ 6000, −128 ≤ Hi ≤ 127

输入样例

输出样例

题解：

考虑一颗以u为根结点的子树，这颗子树的快乐指数应该是u的函数，并且分两种情况，选u和不选u。

状态表示：

f[u][1]: 以u为根结点的子树并且包括u的总快乐指数
f[u][0]: 以u为根结点的子树并且不包括u的总快乐指数

状态计算

记点u的子节点是s1,s2...sk。
1. 选u， f[u][1] += f[s1][0] + f[s2][0] + ... + f[sk][0]
2. 不选u，f[u][0] += max(f[s1][1], f[s1][0]) + ... + max(f[sk][1], f[sk][0])

代码

#include<iostream>
#include<vector>
using namespace std;

const int N = 6000 + 10;

int n, u, v;
vector<int> G[N];
int f[N][2], h[N], fa[N];

void dfs(int u) {
    f[u][1] = h[u];
    for (auto e : G[u]) {
        dfs(e);
        f[u][0] += max(f[e][0], f[e][1]);
        f[u][1] += f[e][0];
    }
}

int main(){
    cin >> n; 
    for (int i = 1; i <= n; ++i) cin >> h[i];
    
    for (int i = 1; i < n; ++i) {
        cin >> u >> v;
        fa[u] = 1;
        G[v].push_back(u);
    }
    
    int root = 1;
    while(fa[root]) root++;
    dfs(root);
    cout << max(f[root][0], f[root][1]);
    return 0;
}

选课

acwing 286

题意

现在有 n 门课程，第 i 门课程的学分为 a[i]，每门课程有零门或一门先修课，有先修课的课程需要先学完其先修课，才能学习该课程。

一位学生要学习 m 门课程，求其能获得的最多学分数。

n,m <= 300

输入格式 第一行包含两个整数n和m，1 <= n <= 300, 1 <= m <= n。接下来 n 行每行代表一门课，课号依次为 1，2，…，n。每行有两个数，第一个数为这门课选修课的课号（若不存在选修课则该项为0），第二个数为这门课的学分。

学分是不超过10的正整数

输出格式 输出一个整数，表示总学分数

输入样例

输出样例

题解：

每门课最多只有一门先修课的特点，与有根树中一个点最多只有一个父亲结点的特点类似。

因此可以想到根据这一性质建树，从而所有课程组成了一个森林的结构。为了方便起见，我们可以新增一门 0学分的课程（设这个课程的编号为 0），作为所有无先修课课程的先修课，这样我们就将森林变成了一棵以0号课程为根的树。

我们设 f(u,i,j)表示以u号点为根的子树中，已经遍历了u号点的前i棵子树，选了j门课程的最大学分。

转移过程结合树形dp和背包dp的特点，我们枚举u点的每个子节点v，同时枚举以v为根的子树选了几门课程，将子树的结果合并到u上。

记点x的儿子个数为s[x]，以x为根的子树大小为siz_x,则可以写出下面转移方程：

f(u,i,j)=max f(u,i-1,j-k) + f(v, s[v], k)

注意上面状态转移方程中的几个限制条件，这些限制条件确保了一些无意义的状态不会被访问到。

的第二维可以很轻松地用滚动数组的方式省略掉，注意这时需要倒序枚举 j 的值。

可以证明，该做法的时间复杂度为 O(nm)。

代码

#include <bits/stdc++.h>

using namespace std;
int f[305][305], s[305], n, m;
vector<int> e[305];

int dfs(int u) {
  int p = 1;
  f[u][1] = s[u];
  for (auto v : e[u]) {
    int siz = dfs(v);
    // 注意下面两重循环的上界和下界
    // 只考虑已经合并过的子树，以及选的课程数超过 m+1 的状态没有意义
    for (int i = min(p, m + 1); i; i--)
      for (int j = 1; j <= siz && i + j <= m + 1; j++)
        f[u][i + j] = max(f[u][i + j], f[u][i] + f[v][j]);  // 转移方程
    p += siz;
  }
  return p;
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1, k; i <= n; i++) {
    scanf("%d%d", &k, &s[i]);
    e[k].push_back(i);
  }
  dfs(0);
  printf("%d", f[0][m + 1]);
  return 0;
}

树的重心

acwing 846

题目

给定一颗树，树中包含n个节点（编号1-n），和n-1条无向边。请你找出树的重心，并输出将重心删除后，剩余各个联通块中点数的最大值。 重心定义：重心是指树中一个节点，如果将这个点删除后，剩余各个连通块中点数的最大值最小。

输入格式 第一行包含整数n,表示树的节点数。1<=n<=1e5 接下来n-1行，每行包含两个整数a和b，表示点a和点b之间有一条边。

输出格式 输出一个整数m，表示将重心删除后，剩余各个连通块中点数的最大值。

输入样例

输出样例

题解

任取一点u，若以u为重心，则分为两类：一类是 u的子树，一类是 u上面的部分

需要算出u的最大子树的节点数和u上面部分的节点数，然后二者取最大值即可。

代码

vector<int> a(n), mx(n);
function<void(int,int)> dfs = [&](int u,int fa) {
    a[u] = 1;
    for (auto v:g[u]) if(v!=fa){
        dfs(v,u);
        a[u]+=a[v];
        mx[u] = max(mx[u], a[v]);
    }
};

dfs(0,-1);
int mn = n;
for (int i = 0; i <n; ++i){
    mn = min(mn, max(mx[i], n - a[i]));
}

树的最长路径

acwing 1072

题目

给定一颗树，树中包含n个节点（编号1-n），和n-1条无向边，每条边都有一个权值。请你找出树中最长的一条路径。换句话说，要找到一条路径，使得路径两端点的距离最远。 “注意”：路径中可能只包含一个点。

输入格式 第一行包含整数n,表示树的节点数。1<=n<=1e4 接下来n-1行，每行包含三个整数a，b, c，表示点a和点b之间有一条权值为c的边。 -1e5 <= c <= 1e5

输出格式 输出一个整数，表示树的最长路径的长度。

输入样例

输出样例

题解

任取一点u，从u点向下搜，返回时收集边的权值，记录两条路径

d1: 记录从u点往下走的最长路径的长度

d2: 记录从u点往下走次长路径的长度

d[u] = d1 + d2, 表示悬挂在u点上的最长路径长度/

因为u是任取一点，所以遍历完所有点，会得到一组d[i]，答案 ans = max(d[i])

不需要开设d数组，每遍历完一个点，及时更新全局变量ans即可

ans = max(ans, d1 + d2)

代码

function<int(int, int)> dfs = [&](int u, int fa) {
    int d1 = 0, d2 = 0;
    for (auto [v, c] : g[u]) 
        if (v != fa) {
            int d = dfs(v, u) + c;
            if (d >= d1) {
                d2 = d1, d1 = d;
            }else if(d>d2){
                d2=d;
            }
        }
    ans=max(ans,d1+d2);
    return d1;
};

树的中心

acwing 1073

给定一颗树，树中包含n个节点（编号1-n），和n-1条无向边，每条边都有一个权值。请你找出树中找到一个点，使得该点到树中其它点的最远距离最近，该点称为树的中心。

输入格式 第一行包含整数n,表示树的节点数。1<=n<=1e4 接下来n-1行，每行包含三个整数a，b, c，表示点a和点b之间有一条权值为c的边。 -1e5 <= c <= 1e5

输出格式 输出一个整数，表示树的中心到树中其它点的最远距离

输入样例

输出样例

题解

点u到其它点的最远距离，可以分为两类：

一类是从u点向下走最远距离，用d1[u]表示

一类是从u点向上走的最远距离，用up[u]表示

从u到其它点的最远距离；max(d1[u], up[u])

从中心到其它点的最远距离： min(max(d1[i], up[i]))

从u点向下走的最远距离d1[u]

从下而上递推，由子节点信息更新父节点信息

从u点向下走的最大长度， d1[u] = d1[j] + w[i]

从u点向下走的次大长度 d2[u] = d2[j] + w[i]

也就是说，在返回时实现，即在dfs后实现

从u点向上走的最远距离up[u]

从上而下递推，由父节点信息更新子节点信息

如果j在从u点向下走的最长路径上 up[j] = w[i]+max(up[u],d2[u])

如果j不在从u点向下走的最长路径上 up[j] = w[i]+max(up[u],d1[u])

也就是说，在下行时实现，即在dfs之前实现

代码

int longestPath(vector<vector<int>> &es) {
    int n=es.size()+1;
    vector<vector<pair<int,int>>> g(n);

    for(auto&e:es){
        g[e[0]-1].emplace_back(e[1]-1,e[2]);
        g[e[1]-1].emplace_back(e[0]-1,e[2]);
    }

    vector<int> d1(n), d2(n), p(n), up(n);
    function<void(int,int)> dfs = [&](int u,int fa) {
        for(auto&[v,c]:g[u]) if(v!=fa){
            dfs(v,u);
            int d=d1[v]+c;
            if(d>=d1[u]){
                d2[u]=d1[u],d1[u]=d,p[u]=v;
            }else if(d>d2[u]) d2[u]=d;
        }
    };
    function<void(int,int)> dfs2 = [&](int u,int fa) {
        for(auto&[v,c]:g[u]) if(v!=fa){
            int d = p[u] == v ? d2[u] : d1[u];
            up[v]=max(up[u],d)+c;
            dfs2(v,u);
        }
    };
    dfs(0,-1);
    dfs2(0,-1);
    int ans=1e9;
    for (int i = 0; i < n; ++i) {
        ans=min(ans,max(up[i],d1[i]));  
    }
    return ans;
}

二叉树染色

leetcode LCP 34

小扣有一个根结点为 root 的二叉树模型，初始所有结点均为白色，可以用蓝色染料给模型结点染色，模型的每个结点有一个 val 价值。小扣出于美观考虑，希望最后二叉树上每个蓝色相连部分的结点个数不能超过 k 个，求所有染成蓝色的结点价值总和最大是多少？

解析

f[i],(0≤i≤k) 表示以该节点为根，相邻的子节点为蓝色的个数为 ii 的情况下（包括自身），节点价值总和的最大值；

当 i=0 时 0时，即表示当前节点为白色，此时无所谓相邻子节点什么颜色，所以当前节点为根价值总和的最大值为左子节点所有情况和右子节点所有情况的最大值，即 f[0] = max(f_l) + max(f_r)
i>0时 f[i]=max(val, fl[j]+fr[i-j-1]) 0 < i ≤ k, 0 < j < i

代码

class Solution {
    vector<int> dfs(TreeNode* root, int k) {
        vector<int> f(k + 1, 0);
        if (!root) return f;
        auto l = dfs(root->left, k), r = dfs(root->right, k);
        f[0] = *max_element(l.begin(), l.end()) + *max_element(r.begin(), r.end());
        for (int i = 1; i <= k; ++i) {
            for (int j = 0; j < i; ++j) {
                f[i] = max(f[i], root->val + l[j] + r[i - j - 1]);
            }
        }
        return f;
    }
public:
    int maxValue(TreeNode* root, int k) {
        auto f = dfs(root, k);
        return *max_element(f.begin(), f.end());
    }
};

监控二叉树

给定一个二叉树，我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

计算监控树的所有节点所需的最小摄像头数量。

分析

维护以下状态

f[i][0]表示以 i 为根的子树本身没有摄像头，且子树内也没有摄像头覆盖它的最小答案。
f[i][1] 表示以 i 为根的子树本身没有摄像头，但子树内的摄像头覆盖到了它的最小答案。
f[i][2] 表示节点 i 本身有摄像头的最小答案。

转移方程,（记节点 i 的左子节点为 l，右子节点为 r）：

f[i][0] = f[l][1] + f[r][1];
f[i][1] = min(f[l][2] + f[r][2], f[l][1] + f[r][2], f[l][2] + f[r][1])
f[i][2] = min(f[l][x] + f[r][y]) + 1 x, y 可取0，1，2

class Solution {
public:
    int minCameraCover(TreeNode* root) {
        const int inf = 1e9;
        function<vector<int>(TreeNode*)> dfs = [&](TreeNode* p) {
            if (!p) return vector<int> {0, 0, inf};
            auto l = dfs(p->left), r = dfs(p->right);
            vector<int> a(3);
            a[0] = min({inf ,l[1] + r[1]});
            a[1] = min({inf, l[2] + r[2], l[2] + r[1], l[1] + r[2]});
            a[2] = inf;
            for (int i = 0; i < 3; ++i) for (int j = 0; j < 3; ++j)
                a[2] = min(a[2], l[i] + r[j] + 1);
            return a;
        };
        auto ans = dfs(root);
        return min(ans[1], ans[2]);
    }
};

换根dp

树形 DP 中的换根 DP 问题又被称为二次扫描，通常不会指定根结点，并且根结点的变化会对一些值，例如子结点深度和、点权和等产生影响。

通常需要两次 DFS，第一次 DFS 预处理诸如深度，点权和之类的信息，在第二次 DFS 开始运行换根动态规划。

最大深度和

洛谷 p3478

给定一个 n 个点的树，请求出一个结点，使得以这个结点为根时，所有结点的深度之和最大。

一个结点的深度之定义为该节点到根的简单路径上边的数量。

解析

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, u, v, x, y;
long long f[N], dep[N], siz[N];
vector<int> g[N];
void dfs(int u, int fa){
    siz[u] = 1;
    dep[u] = dep[fa] + 1;
    for (auto &v: g[u]) {
        if (v != fa) {
            dfs(v, u);
            siz[u] += siz[v];
        }
    }
}
void dfs1(int u, int fa) {
    for (auto &v: g[u]) 
        if (v != fa) {
            f[v] = f[u] - siz[v] * 2 + n;
            dfs1(v, u);
        }
}
int main(){
    scanf("%d",&n);
    for (int i = 0; i <= n; ++i) g[i].clear();
    for (int i = 0; i < n - 1; ++i) {
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 1);
    for (int i = 1; i <= n; ++i) f[1] += dep[i];
    dfs1(1, 1);
    long long ans = -1, id;
    for (int i = 1; i <= n; ++i) {
        if (f[i] > ans) ans = f[i], id = i;
    }
    printf("%d\n", id);
}

树中距离之和

leetcode 周赛84 T4

给定一个无向、连通的树。树中有 n 个标记为 0…n-1 的节点以及 n-1 条边。

给定整数 n 和数组 edges ， edges[i] = [ai, bi]表示树中的节点 ai 和 bi 之间有一条边。

返回长度为 n 的数组 answer ，其中 answer[i] 是树中第 i 个节点与所有其他节点之间的距离之和。

vector<int> sumOfDistancesInTree(int n, vector<vector<int>>& es) {
    vector<int> ans(n), dep(n), siz(n);
    vector<vector<int>> g(n);

    function<void(int,int)> dfs = [&](int u, int fa) {
        siz[u] = 1, dep[u] = (fa < 0 ? 0 : dep[fa] + 1);
        for (auto &v : g[u]) 
            if (v != fa) {
                dfs (v, u);
                siz[u] += siz[v];
            }
    };
    function<void(int,int)> dfs1 = [&](int u, int fa) {
        for (auto &v : g[u])
            if (v != fa) {
                ans[v] = ans[u] - siz[v] * 2 + n;
                dfs1(v, u);
            }
    };

    for (auto &e : es) {
        g[e[0]].push_back(e[1]);
        g[e[1]].push_back(e[0]);
    }
    dfs(0, -1);
    ans[0] = accumulate(dep.begin(), dep.end(), 0);
    dfs1(0, -1);
    return ans;
}

去掉一个端点的最长路径和

leetcode 周赛328 T4

一个 n 个节点的无向无根图, 每个节点有一个价值，p[i] 表示第 i 个节点的价值。一条路径的 价值和 是这条路径上所有节点的价值之和。

求从任意节点出发的价值最大的路径与价值最小的路径的差值的最大值。

1 <= n <= 1e5
1 <= p[i] <= 1e5

方法1

由于所有的价值都是正数，因此以 root 为端点的最短路径只能包含一个节点，也就是 root 本身。另外路径需要以 root 为端点，因此题目求的就是：

求一条路径，使得路径的权值之和减去其中一个端点的权值最大

dfs节点u时

mx1 表示在所有枚举过的 u 的子树中，以 u 为端点的最大路径和。
mx2 表示在所有枚举过的 u 的子树中，以 u 为端点且去掉一个叶子结点的最大路径和。

对于当前节点，它有多颗子树，我们一颗颗 DFS，假设当前 DFS 完了其中一颗子树，返回了 [当前带叶子路径和，当前不带叶子路径和]

答案可能取值为 (mx1 + 当前不带叶子路径和, mx2 + 当前带叶子路径和) mx1 更新为 max(mx1, 当前带叶子路径和 + p[u]) mx2 更新为 max(mx2, 当前不带叶子路径和 + p[u])

class Solution {
public:
    long long maxOutput(int n, vector<vector<int>>& es, vector<int>& p) {
        vector<vector<int>> g(n);
        for (auto &e: es) {
            g[e[0]].push_back(e[1]);
            g[e[1]].push_back(e[0]);
        }
        long long ans = 0;
        function<pair<long long, long long>(int,int)> dfs = [&](int u, int fa) {
            long long mx1 = p[u], mx2 = 0;
            for (int v : g[u]) if (v != fa) {
                auto [s1, s2] = dfs(v, u);
                ans = max({ans, mx1 + s2, mx2 + s1});
                mx1 = max(mx1, s1 + p[u]);
                mx2 = max(mx2, s2 + p[u]);
            }
            return pair<long long, long long>{mx1, mx2};
        };
        dfs(0, -1);
        return ans;
    }
};

换根dp

与树的中心类似,

d1[u]: 从u节点往下走，去掉一个叶节点的最长路径
d2[u]: 从u节点往下走，去掉一个叶节点的次长路径
p[u]: u往下走的最长路径是从哪个节点获得的
up[u]: 从u往上走的去掉一个叶节点的最长路径

long long maxOutput(int n, vector<vector<int>>& es, vector<int>& ps) {
    vector<vector<int>> g(n);
    for (auto &e: es) {
        g[e[0]].push_back(e[1]);
        g[e[1]].push_back(e[0]);
    }
    vector<long long> d1(n), d2(n), p(n), up(n);
    function<void(int, int)> dfs = [&](int u, int fa) {
        for (auto &v : g[u]) if (v != fa) {
            dfs(v, u);
            long long d = d1[v] + ps[u];
            if (d >= d1[u]) {
                d2[u] = d1[u], d1[u] = d, p[u] = v;
            }else if(d > d2[u]) d2[u] = d;
        }
    };

    function<void(int, int)> dfs2 = [&](int u, int fa) {
        for (auto &v : g[u]) if (v != fa) {
            long long d = p[u] == v ? d2[u] : d1[u];
            up[v] = max(up[u], d) + ps[v];
            dfs2(v, u);
        }
    };

    dfs(0, -1);
    dfs2(0, -1);

    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        ans = max(ans, max(d1[i], up[i]));
    }
    return ans;
}

树上边权加终点点权最长路径

abc 222 f

输入 n(2≤n≤2e5) 和一棵树的 n-1 条边（节点编号从 1 开始），每条边输入两个端点和边权。然后输入 n 个数 d，d[i] 表示点 i 的点权。

定义 f(x,y) = 从 x 到 y 的简单路径的边权之和，再加上 d[y]。定义 g(x) = max{f(x,i)}，这里 i 取遍 1~n 的所有不为 x 的点。输出 g(1),g(2),…,g(n)。

分析

与树的中心类似,

d1[u]: 以u为根的子树，悬挂在u上的最长简单路径的边权之和，且路径终点不是u。
d2[u]: 以u为根的子树，悬挂在u上的次长简单路径的边权之和，且路径终点不是u。
p[u]: 悬挂在u上的最长简单路径是从哪个子节点获得的。
up[u]: 从u往上走的最长简单路径的边权之和，且路径终点不是u

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, u, v, c;
    cin >> n;

    vector<vector<pair<int, int> >> g(n);
    
    for (int i = 1; i < n ; ++i) {
        cin >> u >> v >> c;
        u--,v--;
        g[u].emplace_back(v,c);
        g[v].emplace_back(u,c);
    }
    vector<long long> w(n);
    for (int i = 0; i < n; ++i) {
        cin >> w[i];
    }

    vector<long long> d1(n), d2(n), p(n), up(n);

    function<void(int, int)> dfs = [&](int u, int fa) {
        for (auto &[v, c] : g[u]) if (v != fa) {
            dfs(v, u);
            long long d = max(w[v], d1[v]) + c;
            if (d >= d1[u]) {
                d2[u] = d1[u], d1[u] = d, p[u] = v;
            } else if (d >= d2[u]) {
                d2[u] = d;
            }
        }
    };

    function<void(int, int)> dfs2 = [&](int u, int fa) {
        for (auto &[v, c]: g[u]) if (v != fa) {
            long long d = p[u] == v ? d2[u] : d1[u];
            up[v] = max({w[u], d, up[u]}) + c;
            dfs2(v, u);
        }
    };

    dfs(0,-1);
    dfs2(0,-1);
  
    for(int i=0;i<n;++i){
        cout<<max(d1[i],up[i])<<"\n";
    }
    return 0;
}

根节点的潜力值

codestudio contest57

给定一棵树，编号(0 ~ n-1), 一个非叶节点的潜力值，定义为其儿子节点中非0潜力值的节点个数。叶子节点的潜力值定义编号i%2。

返回一个数组，a[i]表示节点i为根节点时，i的潜力值。

3 <= n <= 1e5
0 <= u, v < n

vector<int> potentialTree(int n, vector<vector<int>> &es) {
    vector<vector<int>> g(n);
    for(auto&e:es){
        g[e[0]].push_back(e[1]);
        g[e[1]].push_back(e[0]);
    }

    vector<int> p(n), cnt(n), ans(n);
    
    function<void(int, int)> dfs = [&](int u, int fa) {
        for (auto &v: g[u]) if (v != fa) {
            dfs(v, u);
            cnt[u]++;
            if (p[v] > 0) p[u]++;
        }
        if (cnt[u] == 0) p[u] = u % 2;
    }; 

    auto reroot = [&](int u, int v) {
        cnt[u]--, cnt[v]++;
        p[u] = cnt[u] == 0 ? u % 2 : p[u] -= (p[v] > 0);
        p[v] = cnt[v] == 1 ? (p[u] > 0) : p[v] + (p[u] > 0);
    }; 

    function<void(int, int)> dfs2 = [&](int u, int fa) {
        ans[u] = p[u];
        for (auto &v : g[u]) if (v != fa){ 
            reroot(u,v);     
            dfs2(v, u);
            reroot(v,u);   
        }
        
    };

    dfs(0, -1);
    dfs2(0,-1);
    return ans;
}

状态压缩dp

对于一个二进制状态 S ，枚举子集的代码：

for (int s1 = S; s1; s1 = (s1 - 1) & S) {
    s2 = S ^ s1; // s2是s1在S内的补集
}

这样的枚举方法为什么正确？以 (10110) 为例

s1=(10110) → (10100) → (10010) → (10000) → (110) → (100) → (10)

根据例子，上面代码得到的结果是正确的，并且是 把子集按照从大到小的顺序枚举出来的。

实际上，一个集合它自己本身也是自己的一个集合，所以我们从这个集合本身开始枚举。既然是枚举，那我们就先考虑把当前枚举得到的子集先-1，但是这样做不能保证-1后得到的状态是原状态的子集。

但是我们注意到：根据与运算&的性质，我们不难发现如果两个数a，b，a < b，我们对这两个数进行&运算，最后的结果一定是b的子集，因为我们与运算&得到的结果，在二进制中出现1的位，b中一定也是1。

只需证明在 ((s1-1)&S, s1)区间内没有S的子集，

设 s1 = d1 d2 ... dk 1 0 0 ... 0 ，则 s1-1 = d1 d2 ... dk 0 1 1 ... 1

因为s1是S的子集，所以 s0 = d1 d2 ... dk 0 0 0 ... 0 也是S的子集。

考虑 (s1-1)&S 一定是 (s0, s1) 区间内值最大的子集，问题得证。

完成所有工作的最短时间

leetcode 1723

给你一个整数数组 jobs ，其中 jobs[i] 是完成第 i 项工作要花费的时间。

请你将这些工作分配给 k 位工人。所有工作都应该分配给工人，且每项工作只能分配给一位工人。工人的工作时间是完成分配给他们的所有工作花费时间的总和。请你设计一套最佳的工作分配方案，使工人的 最大工作时间 得以 最小化 。

返回分配方案中尽可能最小的 最大工作时间 。

解析

f[i][j] 表示给前 i 个人分配工作，工作的分配情况为 j 时，完成所有工作的最短时间。注意这里的 j 是一个二进制整数，表示了工作的分配情况。实际上我们也可以将 j 看作一个集合，包含了已经被分配的工作。

    int minimumTimeRequired(vector<int>& jobs, int k) {
        int n = jobs.size();
        vector<int> sum(1 << n);
        for (int i = 1; i < (1 << n); ++i) {
            for (int j = 0; j < n; ++j) {
                if ((i >> j) & 1) sum[i] += jobs[j];
            }
        }
        vector<vector<int>> dp(k, vector<int>(1 << n));
        for (int i = 0; i < (1 << n); i++) {
            dp[0][i] = sum[i];
        }
        for (int i = 1; i < k; ++i) {
            for (int j = 1; j < (1 << n); ++j) { 
                dp[i][j] = INT_MAX;
                for (int x = j; x; x = (x-1)&j) { //枚举状态j的所有子集
                    dp[i][j] = min(dp[i][j], max(dp[i-1][j^x],sum[x]));
                }
            }
        }
        return dp[k-1][(1<<n)-1];
    }

完成任务的最少工作时间段

周赛256 T3

你被安排了 n个任务。任务需要花费的时间用长度为 n的整数数组tasks表示，第 i 个任务需要花费 tasks[i] 小时完成。一个 工作时间段 中，你可以至多连续工作 sessionTime 个小时，然后休息一会儿。

你需要按照如下条件完成给定任务：

如果你在某一个时间段开始一个任务，你需要在同一个时间段完成它。
完成一个任务后，你可以立马开始一个新的任务。
你可以按任意顺序完成任务。

给你 tasks 和 sessionTime ，请你按照上述要求，返回完成所有任务所需要的最少数目的 工作时间段 。

测试数据保证 sessionTime 大于等于 tasks[i] 中的最大值。

数据范围

n == task.length
1 <= n <= 14, 1 <= task[i] <= 10
max(task[i]) <= sessionTime <= 15

解析

f[s] 表示完成任务集合s的所有任务所需要的最少数目的工作时间段。枚举 s 的子集 sub, 若完成 sub 的所有任务耗时不超过 sessionTime，，则可以将 sub 的所有任务用一个工作时间段来完成，也就是将f[s\sub]+1 转移到 f[s]上，这里 s\sub 表示从s中去掉sub的剩余集合。为了节约时间，预处理计算出每一个子集的和。之后采用枚举子集的方式进行动态规划即可。

    int minSessions(vector<int>& tasks, int t) {
        int n = tasks.size();
        vector<int> sum(1<<n);
        for(int i = 1; i < (1 << n); ++i) {
            for (int j = 0; j < n; ++j) 
                if (i & (1 << j)) {
                    sum[i] = sum[i^(1<<j)] + tasks[j];
                    break;
                }
        }

        vector<int> dp(1 << n, 1e9);
        dp[0] = 0;
        for (int i = 1; i < (1 << n); ++i) {
            for (int j = i; j; j = (j - 1) & i)
                if (sum[j] <= t) dp[i] = min(dp[i], dp[i ^ j] + 1);
        }
        return dp[(1<<n)-1];
    }

线段树优化dp

最小可能后缀和

cfgym430673 f

对于一个数组a, 可以将其划分为若干段，在满足每一段的元素和单调不减的条件下，求最后一段元素和的最小值sm。

现在给定数组a，求每个a的非空前缀数组的sm值。

1 <= n <= 2e5
1 <= a[i] <= 1e9

分析

假设我们求第i个前缀数组的sm最小值，希望该数组的一个后缀和最小，即求一个最大的下标p 满足: ans[p] <= a[p+1] + ... + a[i]

对于所有大于p的下标x，都满足 ans[x] > a[x+1]+...+a[i] = s[i + 1] - s[x + 1]

即 min(a[x] + s[x + 1], a[x + 1] + s[x + 2], ... , a[i - 1] + s[i]) > s[i + 1]

可以用线段树维护 a[i] + s[i + 1] 的最小值，对于每个i在线段树上二分最小的x下标。

const long long inf = 1e18;
using S = long long;
S op(S x, S y) { return min(x, y);}
S e() { return inf;}

vector<long long> prefixMinSum(vector<int> &a) {
    int n = a.size();
    vector<long long> s(n + 1), ans(n);
    for (int i = 0; i < n; ++i) {
        s[i + 1] = s[i] + a[i];
    }
    SegTree<S, op, e> seg(n);
    for (int i = 0; i < n; ++i) {
        int p =  i == 0 ? 0 : seg.min_left(i, [&](long long x){
            return x > s[i + 1];
        });
        ans[i] = s[i + 1] - s[p];
        seg.set(i, ans[i] + s[i + 1]);
    }
    return ans;
}

数组最长分段和

cf 1788E

在数组a中选择若干段a[x..y]组成集合S，满足S中每一个分段的和都大于等于0，且各段之间没有交集，定义f(S)为所有段的长度之和，求f(S)的最大值。

1 <= n <= 1e5
-1e9 <= a[i] <= 1e9

分析

设s为a的前缀和数组，f[i]表示前i个元素能获得的最大值.

如果不选第i个元素 f[i] = f[i - 1]
如果选第i个元素，对于所有s[j]小于等于s[i]的j，f[i]=max(f[i], f[j] + j - i)

用线段树维护 f[i] - i, 对前缀和数组进行离散化后，可以直接求出 max(f[j] - j)对最大值。

void ac_yyf(int tt) {
    int n;
    cin >> n;
    vector<long long> s(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> s[i];
        s[i] += s[i - 1];
    }
    Discrete<long long > v(s);
    SegTree<S, op, e> seg(n + 1);
    vector<int> f(n + 1);
    for(int i = 0;i <= n; ++i){
        int id = v(s[i]);
        f[i] = i == 0 ? 0 : max(f[i - 1], i + seg.get(0, id + 1));
        seg.set(id, f[i] - i);
    }
   cout << f[n] << "\n";
}

环形动态规划

环上相邻位置数字不同的方案数

abc307e

n给人站成一个环，每个人可以赋值0-m-1中的数字，求每个人和相邻的人数字都不同的方案数，模998244353。

2 <= n, m <= 1e6

分析

dp[i][0]: 前i个人，且第i个人和第一个人数字相同的方案数 dp[i][1]: 前i个人，且第i个人和第一个人数字不同的方案数

int distince_adj(int n, int m) {
    vector<vector<mint>> f(n,vector<mint>(2,0));
    f[0][0] = m;
    for (int i = 0; i < n - 1; ++i) {
        f[i + 1][0] = f[i][1];
        f[i + 1][1] = f[i][0] * (m - 1) * f[i][1] * (m - 2);
    }
    return f[n - 1][1];
}

得到理想队列的原始排列方案数

luogu p3205

对于一个初始序列a(所有元素互不相同)的排队方法为：

第一个元素直接插入空的序列中
从第i到第n个元素，如果它比上一个元素大，插入序列最后，否则插入序列最前面

现在给出一个最终序列的数组，求有多少种初始序列，排队之后得到该最终序列，模19650827。

1 <= n <= 1000
1000 <= a[i] <= 2000

分析

f[i][j]:区间[i,j],最后排进去的人放到了i的位置。
g[i][j]:区间[i,j],最后排进去的人放到了i的位置。

把 a[i] 放到第i个位置，有两种插入方式：

a[i] <= a[i+1], 且最后插入的是a[i+1], 转移为：f[i][j]+=f[i+1][j]
a[i] < a[j], 且最后插入的是a[j], 转移为 f[i][j]+=g[i+1][j]

同理，把 a[j] 放到第j个位置，有两种插入方式：

a[j-1]<a[j], 且最后插入的是a[j-1]，转移为 g[i][j] += g[i][j-1]
a[i]<a[j], 且最后插入的是a[i], 转移为 g[i][j] += f[i][j-1]

int count_perm(vector<int> &a) {
    int n = a.size();
    vector<vector<int>> f(n,vector<int>(n)), g(n,vector<int>(n));
    for (int i = 0; i < n; ++i) 
        f[i][i] = 1;
    for (int i = n - 2; i >= 0; --i) {
        for (int j = i + 1; j < n; ++j) {
            if (a[i] < a[i + 1]) f[i][j] =  (f[i][j] + f[i + 1][j]) % mod;
            if (a[i] < a[j]) {
                f[i][j] = (f[i][j] + g[i + 1][j]) % mod;
                g[i][j] = (g[i][j] + f[i][j - 1]) % mod;
            }
            if (a[j] > a[j - 1]) g[i][j] = (g[i][j] + g[i][j - 1]) % mod;
        }
    }
    return  (f[0][n - 1] + g[0][n - 1]) % mod;
}

计数dp

n乘2数组填充方案数

cses 2413

一个n行2列的数组，可以用任意形状矩形不重不漏将数组填满，求方案数，模1e9+7

1 <= n <= 1e6

分析

const int M = 1e9 + 7, N = 1e6 + 2;
long long dp[N][2];

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    dp[1][0] = dp[1][1] = 1;
    for (int i = 2; i < N; ++i) {
        dp[i][0] = (dp[i - 1][0] * 4 + dp[i - 1][1]) % M;
        dp[i][1] = (dp[i - 1][0] + dp[i - 1][1] * 2) % M;
    }

    int t, n;
    cin >> t;
    while (t--) {
        cin >> n;
        cout << (dp[n][0] + dp[n][1]) % M << '\n';
    }
    return 0;
}

king-yyf

king-yyf

动态规划分类选题

Index

树形dp

没有上司的舞会

选课

树的重心

树的最长路径

树的中心

二叉树染色

监控二叉树

换根dp

最大深度和

树中距离之和

去掉一个端点的最长路径和

树上边权加终点点权最长路径

根节点的潜力值

状态压缩dp

完成所有工作的最短时间

完成任务的最少工作时间段

线段树优化dp

最小可能后缀和

数组最长分段和

环形动态规划

环上相邻位置数字不同的方案数

得到理想队列的原始排列方案数

计数dp

n乘2数组填充方案数