笔记汇总

树形DP

void dfs(int u)
{
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        dfs(j);
        for (int k = m - v[u]; k >= 0; k -- )
            for (int t = 0; t <= k; t ++ )
            {
                f[u][k] = max(f[u][k], f[u][k - t] + f[j][t]);
            }
    }
    for (int k = m; k >= v[u]; k -- ) f[u][k] = f[u][k - v[u]] + w[u];
    for (int k = 0; k < v[u]; k ++ ) f[u][k] = 0;
}

void dfs1(int u, int father)
{
    // d1[u] = d2[u] = -INF;  //这题所有边权都是正的，可以不用初始化为负无穷
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == father) continue;
        dfs1(j, u);
        if (d1[j] + w[i] >= d1[u])
        {
            d2[u] = d1[u], s2[u] = s1[u];
            d1[u] = d1[j] + w[i], s1[u] = j;
        }
        else if (d1[j] + w[i] > d2[u])
        {
            d2[u] = d1[j] + w[i], s2[u] = j;
        }
    }
    // if (d1[u] == -INF) d1[u] = d2[u] = 0; //特判叶子结点
}
void dfs2(int u, int father)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == father) continue;
        if (s1[u] == j) up[j] = w[i] + max(up[u], d2[u]);   //son_u  = j，则用次大更新
        else up[j] = w[i] + max(up[u], d1[u]);              //son_u != j，则用最大更新
        dfs2(j, u);
    }
}

void dfs(int u)
{
    f[u][0] = 0, f[u][1] = 1;  //initialize
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        dfs(j);
        f[u][0] += f[j][1];
        f[u][1] += min(f[j][0], f[j][1]);
    }
}

树形$DP$ 就是以不同节点为阶段的线性$DP$。

基环树DP

$max/min$

找环，并处理环上信息。

void dfs_c(int u, int from)
{
    st[u] = ins[u] = true;
    for (int i = h[u]; ~i; i = ne[i])
    {
        if (i == (from ^ 1)) continue;  // ^&|优先级小于==!=
        int j = e[i];
        fu[j] = u, fw[j] = w[i];
        if (!st[j]) dfs_c(j, i);
        else if (ins[j])    // 这点出现在栈里，出现环
        {
            cnt ++ ;    // 环的数量 + 1
            ed[cnt] = ed[cnt - 1];  // 新编号
            LL sum = w[i];
            for (int k = u; k != j; k = fu[k])  // 往回走
            {
                s[k] = sum; // 前缀和
                sum += fw[k];
                cir[ ++ ed[cnt]] = k;
            }
            s[j] = sum, cir[ ++ ed[cnt]] = j;
        }
    }
    ins[u] = false;     // 不能继续往下搜了，所以在计算贡献之后就出栈。
    // 搜单条链上的环的技巧
}

计算树上贡献。

LL dfs_d(int u)
{
    st[u] = true;
    LL d1 = 0, d2 = 0;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (st[j]) continue;
        LL dist = dfs_d(j) + w[i];
        if (dist >= d1) d2 = d1, d1 = dist;
        else if (dist > d2) d2 = dist;
    }
    ans = max(ans, d1 + d2);
    return d1;
}

计算环两侧点的最大贡献。

for (int j = 0; j < sz; j ++ )
    d[sz + j] = d[j], sum[sz + j] = sum[j] + sum[sz - 1];
int hh = 0, tt = -1;
for (int j = 0; j < sz * 2; j ++ )
{
    if (hh <= tt && j - q[hh] >= sz) hh ++ ;
    if (hh <= tt) ans = max(ans, d[j] + sum[j] + d[q[hh]] - sum[q[hh]]);
    while (hh <= tt && d[q[tt]] - sum[q[tt]] <= d[j] - sum[j]) tt -- ;
    q[ ++ tt] = j;
}
res += ans;

$count$

从每个环的终点出发，通过删掉某一条边，转化成树计算贡献。

然后通过恰当的条件和赋值，保证计算的状态等价于把断开的位置强制相连，

并用 $DP$ 解决。

void dfs_f(int u, int ap, LL f[][2])
{
    for (int i = h[u]; i != -1; i = ne[i])
    {
        if (rm[i]) continue;
        int j = e[i];
        dfs_f(j, ap, f);
        f[u][0] += max(f[j][0], f[j][1]);
    }
    f[u][1] = -INF;
    if (u != ap)
    {
        f[u][1] = w[u];
        for (int i = h[u]; i != -1; i = ne[i])
        {
            if (rm[i]) continue;
            int j = e[i];
            f[u][1] += f[j][0];
        }
    }
}

void dfs_c(int u, int from)
{
    st[u] = ins[u] = true;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j]) dfs_c(j, i);
        else if (ins[j])
        {
            rm[i] = 1;
            dfs_f(j, -1, f1);
            dfs_f(j, u, f2);
            ans += max(f1[j][0], f2[j][1]);
        }
    }
    ins[u] = false;
}

区间DP

 for (int len = 2; len <= n; len ++ )    // DP的阶段
        for (int l = 1, r; r = l + len - 1, r < 2 * n; l ++ )   // <=[l,r] 都是状态
        {
            for (int k = l; k < r; k ++ )   // DP的决策
            {
                fu[l][r] = max(fu[l][r], fu[l][k] + fu[k + 1][r] + s[r] - s[l - 1]);
                fd[l][r] = min(fd[l][r], fd[l][k] + fd[k + 1][r] + s[r] - s[l - 1]);
            }
        }

int dp(int l, int r)
{
    if (~f[l][r]) return f[l][r];                    //记忆化搜索
    if (l == r) return g[l][r] = l, f[l][r] = w[l];  //题设只有一个节点时，分数就是权值
    if (l > r) return f[l][r] = 1;                   //题设空子树的分数为1
    int score = -INF;
    for (int root = l, t; root <= r; ++ root)
        if ((t = dp(l, root - 1) * dp(root + 1, r) + w[root]) > score)
            score = t, g[l][r] = root;
    return f[l][r] = score;
}

状态压缩DP

// 预处理合法状态
for (int i = 0; i < 1 << n; i ++ )
    if (条件 1)
    {
        cnt[i] = count(i);
        state.push_back(i);
    }

int count(int state)
{
    int res = 0;
    for (int i = 0; i < n; i ++ ) res += state >> i & 1;

    return res;
}

// 预处理合法状态的合法转移
for (int i = 0; i < state.size(); i ++ )
    for (int j = 0; j < state.size(); j ++ )
    {
        int a = state[i], b = state[j];
        if (条件1 ...&& 条件 n)
        {
            head[i].push_back(j);
        }
    }

f[0][0][0] = 1;
for (int i = 1; i <= n + 1; i ++ )                      
    for (int j = 0; j <= k; j ++ )     
        ...
        for (int a = 0; a < state.size(); a ++ )        // 此行可能状态数
            for (int b = 0; b < head[a].size(); b ++ )  // 合法的上一行状态数
            ...
            {
                int c = cnt[state[a]];
                if (j >= c) f[i][j][a] += f[i - 1][j - c][head[a][b]];
            }
printf("%lld", f[n + 1][k][0]);

预处理合法状态和合法转移后，按阶段设计转移方程。

可以滚动数组优化空间。

三进制状压

int dfs(int u, int last, int now, int cnt, int pos, int pre)
{
    if (pos == m)
    {
        return f[u][now] = max(f[u][now], f[u-1][last] + cnt);
    }
    int dgt = last / p[pos] % 3;
    if (dgt == 2) return dfs(u, last, now + p[pos], cnt, pos + 1, pre);
    if (dgt == 1) return dfs(u, last, now, cnt, pos + 1, pre);
    if (pos - pre > 2 && str[u][pos] == 'P') dfs(u, last, now + p[pos] * 2, cnt + 1, pos + 1, pos);
    dfs(u, last, now, cnt, pos + 1, pre);
}

p[0] = 1;
for (int i = 1; i < M; i ++ ) p[i] = p[i-1] * 3;

memset(f, -0x3f, sizeof f);
f[0][0] = 0;
for (int i = 0; i <= n + 1; i ++ )
    for (int j = 0; j < p[m]; j ++ )
    {
        if (f[i][j] < 0) continue;
        dfs(i + 1, j, 0, 0, 0, -3);
    }

inline int count(int x, int pos)
{
    return x % pow3[pos] / pow3[pos-1];
}

inline bool check(int x, int pos, int last) // 第x行第pos位是否能放
{
    return !(g[x][pos] | count(last, m - pos + 1));
}

void dfs(int u, int last, int now, int pos, int cnt)
{
    if (!pos)   // 第u行搜完
    {
        f[u&1][now] = max(f[u&1][now], f[u-1&1][last] + cnt);   
        return;
    }
    if (count(last, pos))   // 上一行pos位有数，去覆盖
    {
        if (g[u][m-pos+1]) return;  // 坐标变换，我们从右往左，但预处理数组是从左往右
        if (count(last, pos) == 2) dfs(u, last, now * 3 + 1, pos - 1, cnt);
        else dfs(u, last, now * 3, pos - 1, cnt);
    }
    else    // 去填数
    {
        dfs(u, last, now * 3, pos - 1, cnt);    // 不填数
        if (pos >= 2 && check(u, m - pos + 1, last) && check(u, m - pos + 2, last))
        {
            dfs(u, last, (now*3+2)*3+2, pos - 2, cnt + 1);
        }
        if (pos >= 3 && check(u, m - pos + 1, last) && check(u, m - pos + 2, last) && check(u, m - pos + 3, last))
        {
            dfs(u, last, ((now*3+1)*3+1)*3+1, pos - 3, cnt + 1);
        }
    }
}

pow3[0] = 1;
for (int i = 1; i <= 10; i ++ ) pow3[i] = pow3[i-1] * 3;

memset(f, -0x3f, sizeof f);
f[0][0] = 0;
for (int i = 0; i < n; i ++ ) 
{
    for (int j = 0; j < pow3[m]; j ++ ) f[i+1&1][j] = -INF;
    for (int j = 0; j < pow3[m]; j ++ ) 
    {
        if (f[i&1][j] < 0) continue;
        dfs(i + 1, j, 0, m, 0);
    }
}
printf("%d\n", f[n&1][0]);  // 目标状态优化

sos DP

/*可维护RMQ和前缀和可以维护的信息*/
// 子集
for (int i = 0; i < n; i ++ )
    for (int j = 0; j < (1 << n); j ++ )
    {
        if ((j >> i) & 1) f[j] += f[j - (1 << i)];
    }
// 超集
for (int i = 0; i < n; i ++ )
    for (int j = 0; j < (1 << n); j ++ )
    {
        if (!((j >> i) & 1)) f[j] += f[j + (1 << i)];
    }
// 子集差分
for (int i = 0; i < n; i ++ )
    for (int j = 0; j < (1 << n); j ++ )
    {
        if ((j >> i) & 1) f[j] -= f[j - (1 << i)];
    }
// 本质是状压DP

数位DP

int dfs(int pos, int st, int op, int lead) {
    if (!pos) {
        边界条件
    }
    if (!op && !lead && f[pos][st] != -1) return f[pos][st];
    int res = 0, up = op ? a[pos] : 无限制位;
    for (int i = 0; i <= up; i ++) {
        if (不合法条件) continue;
        res += dfs(pos - 1, 未定参数, op && i == 数位上界, lead && !i);
    }
    return op ? res : (lead ? res : f[pos][st] = res);
}
int cal(int x) {
    memset(dp, -1, sizeof dp);
    len = 0;
    while (x) a[++ len] = x % 进制, x /= 进制;
    return dfs(len, 未定参数, 1, 1);
}

数字三角形模型

for (int i = 1; i <= r; i ++ )
    for (int j = 1; j <= c; j ++ )
    {
        d[i][j] = max(d[i - 1][j] + g[i][j], d[i][j - 1] + g[i][j]);
    }

memset(d, 0x3f, sizeof d);  // 求最小值取最大

d[1][1] = g[1][1];  // 初始化

for (int i = 1; i <= n; i ++ )
    for (int j = 1; j <= n; j ++ )
    {
        d[i][j] = min(d[i][j], d[i - 1][j] + g[i][j]);
        d[i][j] = min(d[i][j], d[i][j - 1] + g[i][j]);
    }

这里分开是 因为f[1][1]不是从f[0][1]或f[1][0]转移过来的

可以选择将$f[0][1]$和$f[1][0]$置为$0$

int dp(int x, int y)
{
    if (f[x][y] >= 0) return f[x][y];
    if (x == 1 && y == 1) return w[x][y];
    if (x < 1 || y < 1) return INF;

    int t = INF;
    t = min(t, dp(x - 1, y));
    t = min(t, dp(x, y - 1));
    return f[x][y] = t + w[x][y];
}

inline bool check(int x, int y)
{
    return x >= 1 && x <= n && y >= 1 && y <= m;
}
inline LL dfs(int x, int y, int k)
{
    LL &ans = f[x][y][k];
    if (ans != -INF)
    {
        return ans;
    }

    st[x][y] = true;

    if (k == 0) ans = max(ans, Right(x, y));
    if (k == 1) ans = max(ans, Up(x, y));
    if (k == 2) ans = max(ans, Left(x, y));

    st[x][y] = false;
    return ans;
}

由右边转移过来的不可能由左转移过去，由左转移过来的同理。

$st$ 的作用是去环，避免重复走到一个格子（拆为一条链），但是不同搜索分支的可以重复搜。

线性DP

上升

for (int i = 1; i <= n; i ++ ) 
{
    f[i] = 1;
    for (int j = 1; j < i; j ++ )
        if (a[i] > a[j])
        {
            f[i] = max(f[i], f[j] + 1);
        }
    res = max(res, f[i]);
}

for (int i = 1; i <= n; i ++ )
{
    if (b[i] > f[cnt]) f[ ++ cnt] = b[i];
    else *lower_bound(f+1, f+cnt+1, b[i]) = b[i];
    // f[i] 是长度为 i 的上升子序列结尾的最小值
}

非严格单调上升

公共

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            f[i][j] = max(f[i][j], f[i-1][j]);
            f[i][j] = max(f[i][j], f[i][j-1]);
            if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i-1][j-1] + 1);
        }
}

  for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]), h[a[i]] = i;
    for (int i = 1; i <= n; i ++ ) scanf("%d", &b[i]), b[i] = h[b[i]];
    /* a 数据映射为单调，b 最长单调必是 a 的子集
    */
    for (int i = 1; i <= n; i ++ )
    {
        if (b[i] > f[cnt]) f[ ++ cnt] = b[i];
        else *upper_bound(f+1, f+cnt+1, b[i]) = b[i];
        // f[i] 是长度为 i 的上升子序列结尾的最小值
    }

$a, b$集合必须都是相同且没有重复，所以是严格单调上升。

公共上升

for (int i = 1; i <= n; i ++ )
{
    int maxv = 1;
    for (int j = 1; j <= n; j ++ )
    {
        f[i][j] = f[i - 1][j];
        if (a[i] == b[j]) f[i][j] = max(f[i][j], maxv);
        if (a[i] > b[j]) maxv = max(maxv, f[i - 1][j] + 1);
    }
}
for (int i = 1; i <= n; i ++ )
{
    ans = max(ans, f[n][i]);
}    

f[i][j]代表所有a[1 ~ i]和b[1 ~ j]中以b[j]结尾的公共上升子序列的集合；

背包

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

for (int i = 1; i <= n; i ++ )
{
    for (int j = m; j >= v[i]; j -- )
    {
        int tmp = INF;
        tmp = min(tmp, f[j - v[i]] + w[i]);
        f[j] = tmp;
    }
}

f[0] = 1;
for (int i = 1; i <= n; i ++ )
    for (int j = m; j >= v[i]; j -- )
    {
        f[j] += f[j - v[i]];
    }

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

f[0] = 1;
for (int i = 1; i <= n; i ++ )
    for (int j = m; j >= 1; j -- )  // 容量
        for (int k = 1; k <= min(j, a[i]); k ++ )   // k = 0 时和只考虑上一种物品时一样
        {
            f[j] = (f[j] + f[j-k]) % mod;
        }
printf("%d", f[m]);

 int cnt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        int a, b, s;
        cin >> a >> b >> s;
        int k = 1;
        while (k <= s)
        {
            cnt ++ ;
            v[cnt] = a * k;
            w[cnt] = b * k;
            s -= k;
            k *= 2;
        }
        if (s > 0)
        {
            cnt ++ ;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }

    n = cnt;

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

for (int i = 1; i <= n; ++ i)
{
    for (int r = 0; r < v[i]; ++ r)
    {
        int hh = 0, tt = -1;
        for (int j = r; j <= m; j += v[i])
        {
            while (hh <= tt && j - q[hh] > s[i] * v[i]) hh ++ ;
            while (hh <= tt && f[(i - 1) & 1][q[tt]] + (j - q[tt]) / v[i] * w[i] <= f[(i - 1) & 1][j]) -- tt;
            q[ ++ tt] = j;
            f[i & 1][j] = f[(i - 1) & 1][q[hh]] + (j - q[hh]) / v[i] * w[i];
        }
    }
}
cout << f[n & 1][m] << endl;

for (int i = 1; i <= n; i ++ )
    for (int j = m; j >= 0; j -- )
        for (int k = 0; k < s[i]; k ++ )
            if (v[i][k] <= j)
                f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);

int v = V;  // 记录当前的存储空间

// 因为最后一件物品存储的是最终状态，所以从最后一件物品进行循环
for (从最后一件循环至第一件)
{
  if (g[i][v])
  {
    选了第 i 项物品;
    v -= 第 i 项物品的价值;
  } else
    未选第 i 项物品;
}

根据贪心原理，当 费用相同 时，只需保留价值最高的

当 价值一定 时，只需保留费用最低的