动态规划 刷题记录

AT_DP_C Vacation

洛谷 Link

▶

题意

有 $N$ 天，对于每一天 $i$（$1 \leq i \leq N$），可以选择以下活动之一：

• A：在海里游泳，获得幸福度 $a _ i$。
• B：在山上抓虫，获得幸福度 $b _ i$。
• C：在家做作业，获得幸福度 $c _ i$。

不能连续两天以上做同样的活动，计算最大总幸福度。

Solution

DP 板子题。设 $f_{i,j}$ 表示截止到第 $i$ 天时做第 $j$ 件事的幸福值总和。

则易得转移方程为：

$$f_{i,1}=\max(f_{i-1,2},f_{i-1,3})\\ f_{i,2}=\max(f_{i-1,1},f_{i-1,3})\\ f_{i,3}=\max(f_{i-1,1},f_{i-1,2})$$

Core Code

for(int i=1;i<=n;i++)
{
    f[i][1]=max(f[i-1][2],f[i-1][3])+a[i];
    f[i][2]=max(f[i-1][1],f[i-1][3])+b[i];
    f[i][3]=max(f[i-1][1],f[i-1][2])+c[i];
}

AT_DP_K Stones

洛谷 Link

▶

题意

$N$ 个正整数组成的集合 $A = \{ a _ 1, a _ 2, \ldots, a _ N \}$。太郎君和次郎君将用以下游戏进行对决。

首先，准备一个有 $K$ 个石子的堆。两人依次进行以下操作。太郎君先手。

• 从集合 $A$ 中选择一个元素 $x$，从石堆中恰好移除 $x$ 个石子。

不能进行操作的人输掉游戏。当两人都按照最优策略行动时，判断谁会获胜。

Solution

显然当一名玩家操作完成后石子数量为 $0$，则这名玩家必胜。

设 $f_i$ 表示剩余 $i$ 枚石子当前操作的人的输赢情况 ($1/0$)，可以发现当且仅当当前操作的上一步操作必输，当前操作才可以必胜，即如果有 $a_j$ 使得 $f_{i-a_j}=0$，则 $f_i=1$。

初始化 $f_0=0$，则有：

$$f_i=\begin{cases} 1,&a_j\leq i,f_{i-a_j}=0\\ 0 ,& \text{otherwise.} \end{cases}$$

Core Code

f[0]=0;
for(int i=1;i<=k;i++)
{
    for(int j=1;j<=n;j++)
    {
        if(i-a[j]>=0 && !f[i-a[j]]) f[i]=1;
    }
}

AT_DP_M Candies

Link

$K$ 颗糖分给 $n$ 个人，第 $i$ 个人至少分得 $0$ 颗，至多分得 $a_i$ 颗，必须分完，求方案数，答案对 $10^9+7$ 取模。

tag: 背包 DP, 前缀和

Solution

类似背包的处理思路，设 $f_{i,j}$ 表示第 $i$ 个人分完后已经分了 $j$ 个糖，它可以由上一步的 $(j-a_i)\sim j$ 转移得到，所以

$$f_{i,j}=\sum^j_{k=\max(0,j-a_i)}f_{i-1,k}$$

考虑优化时间，滚动数组不可行。发现每一个 $i$ 对应的值都由 $i-1$ 中连续一段的值转移而来，想到用滚动的前缀和维护 $i-1$ 的所有 $f$ 值。

Core Code

int calc(int l,int r) {
    if(l==0) return sum[r];
    return sum[r]-sum[l-1];
}
int main() {
    f[0][0]=1;
    for(int i=1;i<=n;i++) {
        sum[0]=f[i-1][0];
        for(int j=1;j<=m;j++) {
            sum[j]=(sum[j-1]+f[i-1][j]+mod)%mod;
        }
        for(int j=0;j<=m;j++) {
            f[i][j]=(calc(max(0ll,j-a[i]),j)+mod)%mod;
        }
    }
    printf("%lld\n",f[n][m]%mod);
}

AT_DP_P Independent Set

Link

给一棵树，每一个点可以染成黑色或白色，任意两个相邻节点不能都是黑色，求方案数。

tag: 树形 DP

Solution

设 $f_{u,0/1}$ 表示 $u$ 节点染成 W/B 颜色时的方案数。DFS 子树的方案数，可以得到：

$$\begin{aligned} f_{u,0}&=\prod_{v\in u}(f_{v,0}+f_{v,1})\\ f_{u,1}&=\prod_{v\in u}f_{v,0} \end{aligned}$$

注意 $1$ 号点为根，输入无序需建双向边。

Core Code

void dfs(int u) {
    g.vis[u]=1;
    f[u][0]=f[u][1]=1;
    for(int i=0;i<e[u].size();i++) {
        int v=e[u][i];
        if(!g.vis[v]) {
            dfs(v);
            f[u][0]=(f[u][0]*(f[v][0]+f[v][1]))%mod;
            f[u][1]=(f[u][1]*f[v][0])%mod;
        }
    }
}

AT_DP_Q Flowers

Link

有一排花，共 $n$ 个，第 $i$ 个的高度是 $h_i$，权值是 $a_i$，保证高度互不相同。现在拿走一些花，使剩下的花高度单调递增，问剩下的花权值之和最大是多少。

tag: 线段树优化 DP

Solution

带权的最长上升子序列，设 $f_i$ 表示第 $i$ 个元素结尾的最大答案，可以参照最长上升子序列写出转移方程

$$f_{i}=\max_{j=1}^{i-1}\{f_{j}|h_j<h_i\}+a_{i}$$

考虑优化，观察到转移方程是区间最大值，想到用值域线段树优化。将 $h_i$ 作为线段树的下标，对应当前高度时的 $f_i$。

Core Code

struct node {
    ll val;
}t[N * 4];
struct tree {
    void pushup(int p) {
        t[p].val = max(t[p * 2].val, t[p * 2 + 1].val);
    }
    void modify(int p, int l, int r, int x, ll k) {
        if (l == r) {
            t[p].val = k;
            return;
        }
        int mid = (l + r) >> 1;
        if (x <= mid) modify(p * 2, l, mid, x, k);
        else modify(p * 2 + 1, mid + 1, r, x, k);
        pushup(p);
    }
    ll query(int p, int l, int r, int x, int y) {
        if (x <= l && r <= y) {
            return t[p].val;
        }
        ll res = 0;
        int mid = (l + r) >> 1;
        if (x <= mid) res = max(res, query(p * 2, l, mid, x, y));
        if (y >= mid + 1) res = max(res, query(p * 2 + 1, mid + 1, r, x, y));
        return res;
    }
}sgt;
int main() {
    n = read();
    for (int i = 1; i <= n; i++) {
        h[i] = read();
    }
    for (int i = 1; i <= n; i++) {
        a[i] = read();
    }
    for (int i = 1; i <= n; i++) {
        f[i] = sgt.query(1, 1, n, 1, h[i]) + a[i];
        sgt.modify(1, 1, n, h[i], f[i]);
    }
    cout << sgt.query(1, 1, n, 1, n) << endl;
    return 0;
}

AT_DP_T Permutation

Link

有一个长为 $N$ 的正整数排列。给定一个由 < 和 > 组成长为 $N-1$ 的的字符串。对于任意满足 $1 \le i \le N-1$ 的字符 $s_i$，如果 $s_i$ 是 < 则 $P_i<P_{i+1}$、如果 $s_i$ 是 > 则 $P_i>P_{i+1}$。求满足这样的性质的排列 $P$ 的方案数。

Solution

由于 $p$ 是排列，我们不在意 $p$ 中到底放了什么数，只需要关注当前一步放的数和上一步放的数的大小关系。可以得到状态 $f_{i, j}$ 表示前 $i$ 个数形成的排列中，第 $i$ 个数是第 $j$ 大的方案数。

在转移时，若当前填的数需大于前一个数，那么直接得到 $f_i=\sum_{k=1}^{j-1}f_{i-1,k}$。

若小于前一个数，可以将 $p_1\sim p_{i-1}$ 中 $\geq j$ 的数全部加 $1$，保证组成的是排列，这等价于遍历的排名 $k$ 都减一（自行手玩样例），$f_{i}=\sum_{k=j}^{i-1}f_{i-1,k}$。

注意到转移是求连续一段的和，前缀和优化即可。

Core Code

f[1][1] = 1;
for (int i = 1; i <= n; i++) {
    sum[i][1] = 1;
}
for (int i = 2; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
        if(s[i-1] == '>') {
            f[i][j] = (f[i][j] + sum[i-1][i-1] - sum[i-1][j-1] + mod) % mod;
        } else {
            f[i][j] = (f[i][j] + sum[i-1][j-1] + mod) % mod;
        }
        sum[i][j] = (sum[i][j-1] + f[i][j] + mod) % mod;
    }
}
int ans = 0;
for (int i = 1; i <= n; i++) {
    ans = (ans + f[n][i] + mod) % mod;
}

AT_DP_W Intervals

Link

给定 $m$ 条规则形如 $(l_i,r_i,a_i)$，对于一个 01 串，其分数的定义是：对于第 $i$ 条规则，若该串在 $[l_i,r_i]$ 中至少有一个 1，则该串的分数增加 $a_i$。

你需要求出长度为 $n$ 的 01 串中的最大分数。

tag: 线段树优化 DP, 区间右端点排序

Solution

首先将区间按右端点排序，在右端点处统计答案。

考虑 DP，设 $f_{i,j}$ 表示前 $i$ 个位置中最后一个 $1$ 的位置为 $j$ 的最大分数。

不难想到 $f_{i,j}=\max_{k=1}^j f_{i-1,k}+\sum_{l_p\leq k\text{ and }r_p=i} a_p$。即使 $[l, r]$ 覆盖到 $k$ 位置。

对上式进行优化，发现可以贪心的使 $1$ 的位置尽量靠后，才能最大化 $1$ 的数量，所以 $f_{i,j}=f_{i-1,j}+\sum_{l_k\leq j\text{ and }r_k=i}a_k$。

优化后，会有 $j=i$ 的特殊情况，此时上一步选的 $1$ 可以在任意位置，取最大值即可。最终转移方程即为：

$$f_{i,j}= \begin{cases} \max_{k=1}^{j-1} f_{i-1,k}+\sum_{r_p=i} a_p,&i=j\\ f_{i-1,j}+\sum_{l_k\leq j\text{ and }r_k=i} a_k,&i\neq j \end{cases}$$

滚动掉一维后，发现枚举位置 $i$ 时，如果 $r_j=i$，那么这段区间 $[l_j, r_j]$ 会在 $[l_j, i]$ 中做出 $a_j$ 的贡献。扔到线段树上区间加区间查询最大值即可。

Core Code

struct query {
    int l, r, a;
    bool operator<(const query &x) const {
        return r < x.r;
    }
}q[N];
struct node {
    int val, tag;
};
struct tree {
    node t[4 * N];
    void mktag(int p, int w) {
        t[p].val += w;
        t[p].tag += w;
    }
    void pushdown(int p) {
        if (t[p].tag) {
            mktag(p * 2, t[p].tag);
            mktag(p * 2 + 1, t[p].tag);
            t[p].tag = 0;
        }
    }
    void pushup(int p) {
        t[p].val = max(t[p * 2].val, t[p * 2 + 1].val);
    }
    void modify(int p, int l, int r, int x, int y, int w) {
        if (x <= l && r <= y) {
            mktag(p, w);
            return;
        }
        pushdown(p);
        int mid = (l + r) >> 1;
        if (x <= mid) modify(p * 2, l, mid, x, y, w);
        if (y >= mid + 1) modify(p * 2 + 1, mid + 1, r, x, y, w);
        pushup(p);
    }
    int query(int p, int l, int r, int x, int y) {
        if (x <= l && r <= y) {
            return t[p].val;
        }
        pushdown(p);
        int mid = (l + r) >> 1;
        int res = 0;
        if (x <= mid) res = max(res, query(p * 2, l, mid, x, y));
        if (y >= mid + 1) res = max(res, query(p * 2 + 1, mid + 1, r, x, y));
        return res;
    }
}sgt;
signed main() {
    n = read(); m = read();
    for (int i = 1; i <= m; i++) {
        q[i].l = read(), q[i].r = read(), q[i].a = read();
    }
    sort(q + 1, q + m + 1);
    int nw = 1;
    for (int i = 1; i <= n; i++) {
        if (i != 1) sgt.modify(1, 1, n, i, i, sgt.query(1, 1, n, 1, i - 1));
        while (q[nw].r == i && nw <= m) {
            sgt.modify(1, 1, n, q[nw].l, i, q[nw].a);
            nw++;
        }
    }
    cout << max(0ll, sgt.query(1, 1, n, 1, n)) << endl;
    return 0;
}

TDPC_IWI イウィ

洛谷 Link

给定一个仅由字符 $\texttt{i}$ 和 $\texttt{w}$ 构成的字符串 $s$。你可以进行若干次操作，每次从串中选取连续的三个字符 $\texttt{iwi}$ 并删除；每次操作后这三个字符的左侧和右侧会连接在一起，得到一个长度比原来小 $3$ 的新串。求可能的最大操作次数。

tag: 区间 DP

Solution

区间 DP，类似合并石子。

我们定义 $f_{i,j}$ 记录 $i$ 到 $j$ 能删掉多少字符，显然最后答案应除以 $3$。

因为答案计算的是最大的步数，那么对于一个大区间，在一般情况下的答案就应该是其分成的两个小区间的答案之和。考虑枚举这两个区间之间的分界点 $k$，答案取最大值即可。

本题还需要特判一种特殊情况。如果 $s_i$ 和 $s_j$ 为 i，$s_k$ 为 w，且中间的两个小段可以被完全删除。那么，当中间的被删掉之后，左右的 i 和中间的 w 就会拼在一起，也可以删掉，那么这个区间的答案就应该是它的长度，但显然直接相加有可能会出错。

Core Code

for(int a=2;a<=len;a++)
{
    for(int i=1;a+i-1<=len;i++)
    {
        int j=a+i-1;
        for(int k=i;k<j;k++)
        {
            f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]);
            if(s[i]=='i' && s[j]=='i' && s[k]=='w' && f[i+1][k-1] == k-i-1 && f[k+1][j-1] == j-1-k)
            {
                f[i][j]=j-i+1;
            }
        }
    }
}
write(f[1][len]/3);

ABC247F Cards

Link

给定 $ n $ 张卡片，每张卡片正反面各有一个数，给定每张卡片正面和反面的数，保证正面的数构成的序列，和反面的数构成的，分别均为 $ 1 $ 到 $ n $ 的排列，可以选择任意张卡片并获得其正反面的数，要求最终所有获得的数至少包含 $ 1 $ 到 $ n $ 每个数至少一次。求有多少种取法，对 $ 998244353 $ 取模。

tag: 并查集

Solution

trick 题，记住。

想到在两个拥有相同数字的卡片连边，则一个边的两点中必须至少选一个。

由于每张卡有两个数，度数为二，则连完后必定会形成若干个简单环或自环。

根据乘法原理，对于每个环求出方案数后相乘后即为答案。

先上结论，设 $f_i$ 表示一个大小为 $i$ 的环的选择方案数，有如下转移：

$$f_i=f_{i-1}+f_{i-2}$$

考虑证明它，设一个如下图的环，其中 others 表示剩余的所有点。

分类讨论，如果选 $A$ 点，那么 $B$ 和 $C$ 点可以任取。转化为剩余一条不含 $A$ 的链，这样不好考虑，将 $B$ 和 $C$ 连接起来，转化为少一个点的环，这个环的答案是 $f_{i-1}$。但这样还少了一种 $B$ 和 $C$ 都不算的情况，考虑将 $B$ 和 $C$ 缩为一点，将个大点不选的方案数位 $k$。

如果不选 $A$ 点，那么还是上面的链，但 $B$ 和 $C$ 必选，按照上面的处理方式，同样将 $B$ 和 $C$ 缩为一点，这个图的方案数是 $f_{i-2}$。但这样多算了 $B$ 和 $C$ 都不选的贡献，可以发现这部分贡献就是 $k$。

所以可以得到：

$$f_i=f_{i-1}+\not k+f_{i-2}-\not k$$

用并查集存环即可。

Core Code

n = read();
for (int i = 1; i <= n; i++) fa[i] = i;
for (int i = 1; i <= n; i++) {
    t[read()] = i;
}
for (int i = 1; i <= n; i++) {
    q[i] = read();
    merge(i, t[ q[i] ]);
}
for (int i = 1; i <= n; i++) {
    siz[find(i)]++;
}
f[1] = 1ll, f[2] = 3ll;
for (int i = 3; i < N; i++) {
    f[i] = (f[i - 1] + f[i - 2]) % mod;
}
int ans = 1ll;
f[0] = 1ll;
for (int i = 1; i <= n; i++) {
    ans = (ans * f[ siz[i] ] % mod + mod) % mod;
}

ABC336D Pyramid

Link

▶

题意

对于正整数 $k$，一个大小为 $k$ 的“金字塔数列”为一个长度为 $2k-1$ 的数列，里面的数字依次为 $1,2,3,\dots k-1,k,k-1,\dots 3,2,1$。
现在给一个长度为 $n$ 的数列 $S$，你可以进行以下操作任意次，使得数列最后变为一个“金字塔数列”：

• 选择一个数 $i(1 \le i \le n)$，把 $S_i$ 减少 $1$。
• 删除整个数列的第一个或最后一个数字。

问最后生成的“金字塔数列”的最大的 $k$ 是多少。

Solution

显然一个金字塔数列是由左右两部分拼接而成的。设 $f_{i}$ 表示前 $i$ 个数能组成左半部分的最长长度，$g_{i}$ 表示以 $i$ 为首的序列能组成右半部分的最长长度（差不多等价于后 $i$ 个数，但注意转移方程的写法）。一个明显的性质是如果满足可以构成长度为 $x$ 的序列，那么一定可以通过删掉元素构成长度为 $x-1$ 的序列，所以可以发现以 $i$ 为中间项的最长长度即为 $\min\{f_i, g_i\}$。

以 $f$ 为例，假设 $s_i$ 的所有值都是 $+\infty$，可以得到显然的转移方程 $f_{i}=f_{i-1}+1$。如果加上 $s_i$ 的限制条件，那么 $f_i=\min\{f_{i-1}+1, s_i\}$。同理可得 $g_i=\min\{g_{i+1}+1, s_i\}$。

Core Code

n = read();
for (int i = 1; i <= n; i++) {
    a[i] = read();
}
f[1] = g[n] = 1;
for (int i = 2; i <= n; i++) {
    f[i] = min(f[i-1] + 1, a[i]);
}
for (int i = n - 1; i >= 1; i--) {
    g[i] = min(g[i+1] + 1, a[i]);
}
int ans = 0;
for (int i = 1; i <= n; i++) {
    ans = max(ans, min(f[i], g[i]));
}
cout << ans << endl;

SP703 Mobile Service

Problem Link

▶

题意

有 $3$ 个流动员工，任何时刻只有一名员工可以移动，不允许同一位置上有 $2$ 个及以上员工。

从位置 $p$ 移动到位置 $q$ 需要花费 $c(p,q)$ 的价钱，不移动不需要花费（即 $c(i,i)=0$ ）但不保证 $c(p,q)=c(q,p)$。

现在给出 $N$ 个请求，第 $i$ 个请求发生在位置 $x_i$。公司必须按照顺序，派一名员工到位置 $x_i$，过程中不能去其他地方，也就是必须直接过去。

$3$ 个流动员工的初始位置分别为 $1,2,3$。

求公司的最小花费。

tag: DP

Solution

设 $f_{i,x,y,z}$ 表示处理到第 $i$ 个请求，三个人分别在 $x,y,z$ 位置上时的最小值。注意到三个人中一定会有一个人在上一个请求的位置，故状态可以优化为 $f_{i,x,y}$，此时令 $z=q_{i-1}$ 则有

$$f_{i+1,x,y}=\min(f_{i+1,x,y},f_{i,x,y}+c_{z,q_{i+1}})\\ f_{i+1,x,z}=\min(f_{i+1,x,z},f_{i,x,y}+c_{y,q_{i+1}})\\ f_{i+1,y,z}=\min(f_{i+1,y,z},f_{i,x,y}+c_{x,q_{i+1}})$$

初值 $q_0=1, f_{0,2,3}=0$。

Core Code

for(int i=0;i<n;i++) {
    for(int x=1;x<=l;x++) {
        for(int y=1;y<=l;y++) {
            int z=q[i];
            if(x==y || x==z || y==z) continue;
            f[i+1][x][y]=min(f[i+1][x][y],f[i][x][y]+c[z][q[i+1]]);
            f[i+1][z][y]=min(f[i+1][z][y],f[i][x][y]+c[x][q[i+1]]);
            f[i+1][x][z]=min(f[i+1][x][z],f[i][x][y]+c[y][q[i+1]]);
        }
    }
}
int ans=INF;
for(int x=1;x<=l;x++) {
    for(int y=1;y<=l;y++) {
        int z=q[n];
        if(x==y || x==z || y==z) continue;
        ans=min(ans,f[n][x][y]);
    }
}

P4310 绝世好题

Link 和同类题 CF264B Good Sequences

给定一个长度为 $n$ 的数列 $a_i$，求 $a_i$ 的子序列 $b_i$ 的最长长度 $k$，满足 $b_i\ \text{and}\ b_{i-1} \neq 0 $，其中 $2\leq i\leq k$。

tag: 位运算, DP

Solution

设 $f_{i}$ 表示最后一个数为 $a_i$ 的最长长度，$\text{bit}_i$ 表示遍历到当前数二进制位 $i$ 为 $1$ 的数量。

可以注意到只要两个数同一二进制位都为 $1$，那么他们与起来一定不等于 $0$。同时可以注意到上面的结论还可以传递，比如 $(1000)_2\ \text{and}\ (1010)_2\ \text{and}\ (0010)_2\neq 0$。

所以在每次循环时，先通过枚举 $a_i$ 每一个二进制位更新 $f_i$，然后用当前情况的 $f_i$ 去更新 $a_i$ 二进制为为 $1$ 的 $\text{bit}_i$。

$$\begin{cases} f_i&=\max(f_i, \text{bit}_j)\\ \text{bit}_j&=f_i \end{cases} , a_i\ \text{and}\ (1<<j)\neq 0$$

Core Code

for(int i=1;i<=n;i++) {
    for(int j=0;j<=32;j++) {
        if((1<<j)&a[i]) f[i]=max(f[i],bit[j]+1);
    }
    for(int j=0;j<=32;j++) {
        if((1<<j)&a[i]) bit[j]=f[i];
    }
}
int ans=0;
for(int i=1;i<=n;i++) {
    ans=max(ans,f[i]);
}

P1944 最长括号匹配

Problem Link

▶

题意

对一个由 (,),[,] 括号组成的字符串，求出其中最长的括号匹配子串。

1. (),[] 是括号匹配的字符串。
2. 若 A 是括号匹配的串，则 (A),[A] 是括号匹配的字符串。
3. 若 A,B 是括号匹配的字符串，则 AB 也是括号匹配的字符串。

例如：(),[],([]),()() 都是括号匹配的字符串，而 ][,[(]) 则不是。

字符串 A 的子串是指由 A 中连续若干个字符组成的字符串，包含空串。

Solution

设 $f_i$ 表示到 $s_i$ 时最长括号匹配，从头开始线性扫描，扫到后半括号时判断是否能组成匹配。

显然，当且仅当在其 前面括号匹配长度（$f_{i-1}$）的前一个字符是同类型的前半括号（即类似
(xxx)）。

由此可得式子 $f_i=f_{i-1}+f_{i-f_{i-1}-2}+2$。其中 $i-f_{i-1}-2$ 表示前半括号。

Core Code

for(int i=1;i<=n;i++) {
    if((s[i]==')' && s[i-f[i-1]-1]=='(') || (s[i]==']' && s[i-f[i-1]-1]=='[')) f[i]=f[i-1]+f[i-f[i-1]-2]+2;
    if(ans<f[i]) {
        ans=f[i];
        last=i;
    }
}
for(int i=last-ans+1;i<=last;i++) {
    putchar(s[i]);
}
el;

P1284 三角形牧场

Problem Link

给定多个线段，求全部使用情况下最大能围成的三角形周长。

tag: 背包

Solution

显然要用海伦公式求周长，那就需要枚举三角形三条边的长度。由于所有边都需要使用，可以优化为仅枚举两条边的长度。

设 $f_{k,i,j}$ 表示第 $k$ 个边时，是否存在一个两边长为 $i, j$ 的三角形。

类似 01 背包思路，$f_k$ 可以由 $f_{k-1}$ 转移而来，当前的边可以加在 $i,j$ 和第三条边上，也就可以由 $f_{k-1, i-l_k, j}, f_{k-1, i, j-l_k}, f_{k-1, i, j}$ 转移而来

$$f_{k,i,j}= \begin{cases} \text{true}, &f_{k-1,i-l_k,j}=\text{true}\ \text{or}\ f_{k-1,i,j-l_k}=\text{true}\ \text{or}\ f_{k-1,i,j}=\text{true}\\ \text{false}, &\text{otherwise.} \end{cases}$$

同 01 背包一样，$k$ 这一维可以滚动掉。

Core Code

bool check(int a,int b,int c) {
    if(a+b>c && a+c>b && b+c>a) return 1;
    else return 0;
}
double calc(double a,double b,double c) {
    double p=(a+b+c)/2.0;
    return 100.0*sqrt(p*(p-a)*(p-b)*(p-c));
}
int main() {
    f[0][0]=1;
    for(int i=1;i<=n;i++) {
        for(int j=p;j>=0;j--) {
            for(int k=p;k>=0;k--) {
                if(j-l[i]>=0 && f[j-l[i]][k]) f[j][k]=1;
                if(k-l[i]>=0 && f[j][k-l[i]]) f[j][k]=1;
            }
        }
    }
    int ans=-1;
    for(int i=1;i<=p;i++) {
        for(int j=1;j<=p;j++) {
            if(check(i,j,p-i-j) && f[i][j]) ans=max(ans,(int)calc(i,j,p-i-j));
        }
    }
}

P4084 [USACO17DEC] Barn Painting G

Problem Link

给定一颗 $N$ 个节点组成的树，你要给每个点涂上三种颜色之一，其中有 $K$ 个节点已染色，要求任意两相邻节点颜色不同，求合法染色方案数。

tag: 树形 dp

Solution

树形 DP，设 $f_{i,j}$ 为 $i$ 节点颜色 $j$ 的方案数。

若 $i$ 已经被染色 $j$ 了，那显然 $f_{i,j}=1$，其他为 $0$；若未被染色，则 $f_{i,j}=1, j\in [1,3]$。

从下向上转移：

$$\begin{cases} f_{u,1}=\prod_{v\in \text{son}(u)} (f_{v,2}+f_{v,3})\\ f_{u,2}=\prod_{v\in \text{son}(u)} (f_{v,1}+f_{v,3})\\ f_{u,3}=\prod_{v\in \text{son}(u)} (f_{v,1}+f_{v,2}) \end{cases}$$

Core Code

#define int ll
vector<int> e[N];
int n,k;
int f[N][5];
bool is_colored[N];
bool vis[N];
void dfs(int u) {
    vis[u]=1;
    for(int i=0;i<e[u].size();i++) {
        int v=e[u][i];
        if(!vis[v]) {
            dfs(v);
            f[u][1]=(f[u][1]*((f[v][2]+f[v][3]+mod)%mod)+mod)%mod;
            f[u][2]=(f[u][2]*((f[v][1]+f[v][3]+mod)%mod)+mod)%mod;
            f[u][3]=(f[u][3]*((f[v][1]+f[v][2]+mod)%mod)+mod)%mod;
        }
    }
}
signed main() {
    n=read();k=read();
    for(int i=1;i<n;i++) {
        int u=read(),v=read();
        e[u].push_back(v);
        e[v].push_back(u);
    }
    for(int i=1;i<=k;i++) {
        int b=read(),c=read();
        f[b][c]=1;
        is_colored[b]=1;
    }
    for(int i=1;i<=n;i++) {
        if(!is_colored[i]) f[i][1]=f[i][2]=f[i][3]=1;
    }
    dfs(1);
    printf("%lld\n",(f[1][1]+f[1][2]+f[1][3]+mod)%mod);
    return 0;
}

P2458 [SDOI2006] 保安站岗

Link

给定一颗树，每个点有点权 $k$，要求一条边的两个端点至少有一个被占用，求占用整棵树的代价的最小值。

tag: 树形 DP

与 P2016 战略游戏 不同，本题为守点。如 1-2-3-4 本题可以选择 1 和 4，但战略游戏不可。所以本题需要设这三个状态。

本题守点，意味着如果一个点不选，那么只需要与这个点相连的任一点选择即可，而守边则就需要与这个点相连的所有点都选。

Solution

首先不能将状态设为一个点被占或不占，这样会造成向上转移时父节点无法影响子节点。

设 $f_{u,1/2/3}$ 表示 $u$ 节点 自身被占用/被儿子覆盖/被父亲覆盖。

首先第一种情况显然 $f_{u,1}=\sum_{v\in \text{son}(u)}\min(f_{v,1}, f_{v,2}, f_{v,3})+k_u$。

对于第三种情况，由于 $u$ 被父亲覆盖，自身未被占用，那么就需要使 以 $u$ 的儿子 $v$ 为根的子树中的点都被覆盖。问题转化后，只有 $v$ 自身被占用和 $v$ 被儿子覆盖可以满足条件，即 $f_{u,3}=\sum_{v\in \text{son}(u)}\min(f_{v,1}, f_{v,2})$。

对于第二种情况，分析方式类似第三种，首先要满足子树被覆盖。同时，要有至少一个 $v$ 自身被占用，才能影响到 $u$。可以在上面的式子的基础上略加更改，若最小值全部被 $f_{v,2}$ 取到，那么最后再加上所有 $v$ 中 $f_{v,1}$ 最小的一个即可。

最终答案即为 $\min(f_{\text{root},1}, f_{\text{root},2})$。

Core Code

void dfs(int u,int fa) {
    int minn=INF;
    bool flag=0;
    for(auto v:e[u]) {
        if(v==fa) continue;
        dfs(v,u);
        f[u][1]+=min(f[v][1],min(f[v][2],f[v][3]));
        f[u][2]+=min(f[v][1],f[v][2]);
        f[u][3]+=min(f[v][1],f[v][2]);
        minn=min(minn,f[v][1]-f[v][2]);
        if(f[v][1]<f[v][2]) flag=1;
    }
    if(!flag) f[u][2]+=minn;
}
int main() {
    n=read();
    for(int i=1;i<=n;i++) {
        int u=read();
        k[u]=read();
        int m=read();
        f[u][1]=k[u];
        for(int j=1;j<=m;j++) {
            int v=read();
            e[u].push_back(v);
            e[v].push_back(u);
        }
    }
    dfs(1,0);
    cout<<min(f[1][1],f[1][2])<<endl;
    return 0;
}

P2016 战略游戏

Link

给定一颗树，一个节点可以看守相邻的所有节点，求看守整棵树需要的最少的节点数。

tag: 树形 DP

本题与上一题不用的是，本题可以转化为一个点可以看守与这个点相连的所有边。

本题守边，意味着如果一个点不选，那么就需要与这个点相连的所有点都选，而守点则只需要与这个点相连的任一点选择即可。

Solution

设 $f_{u,0/1}$ 表示 $u$ 节点选 / 不选。

如果 $u$ 不选，那么他的所有儿子必选，因为需要满足看守所有的边，$f_{u,0}=\sum_{v\in \text{son}(u)} f_{v,1}$；

如果 $u$ 选，那么他的儿子选不选并不重要，$f_{u,0}=\sum_{v\in \text{son}(u)}\min\{f_{v,0}, f_{v,1}\}$。

Core Code

void dfs(int u,int fa) {
    f[u][1]=1;
    for(auto v:e[u]) {
        if(v==fa) continue;
        dfs(v,u);
        f[u][0]+=f[v][1];
        f[u][1]+=min(f[v][0],f[v][1]);
    }
}

P3478 [POI2008] STA-Station

Link

给出一个 $n$ 个点的树，找出一个点，使以这个点为根的树所有点的深度之和最大

tag: 树形 DP, 换根 DP

Solution

换根板子。

首先考虑如何暴力，显然是以每个点为根都跑一边 dfs，时间复杂度 $\mathcal O(n^2)$。

一般换根 DP 题的处理思路是：

1. 先指定一个根节点，一次 dfs 自下而上，用子节点的值更新父节点；
2. 从上一步的根出发，dfs 转移父节点对子节点的贡献。

设 $f_{u}$ 为以 $u$ 为根的深度和。运用人类智慧可以注意到 $u$ 节点的值可以通过其父亲转移。如下图，我们已经处理好了 $2$ 号节点的答案，那么发现以 $4$ 为根的时，$4$ 的子树（包括自己）的相对深度都减少了 $1$，而 $4$ 上面的三个点深度都增加了 $1$。

可以得到转移方程：

$$f_{v}=f_{u}-\text{siz}_{v}\times 1+(n-\text{siz}_{v})\times 1=f_u+n-2\times \text{siz}_v$$

其中 $\text{siz}_v\times 1$ 表示 $4$ 的子树，$n-\text{siz}_v$ 表示 $4$ 上面的点。

Core Code

void dfs1(int u,int fa) {
    g.siz[u]=1;
    for(auto v:e[u]) {
        if(v==fa) continue;
        g.dep[v]=g.dep[u]+1;
        dfs1(v,u);
        g.siz[u]+=g.siz[v];
    }
}
void dfs2(int u,int fa) {
    for(auto v:e[u]) {
        if(v==fa) continue;
        f[v]=f[u]+n-2ll*g.siz[v];
        dfs2(v,u);
    }
}
int main() {
    dfs1(1,0);
    for(int i=2;i<=n;i++) {
        f[1]+=g.dep[i];
    }
    dfs2(1,0);
    ll ans=-INF,maxn=-INF;
    for(int i=1;i<=n;i++) {
        if(maxn<f[i]) {
            maxn=f[i];
            ans=i;
        }
    }
    cout<<ans<<endl;
    return 0;
}

P3047 [USACO12FEB] Nearby Cows G

Link

给你一棵 $n$ 个点的树，点带权，对于每个节点求出距离它不超过 $k$ 的所有节点权值和 $m_i$。

tag: 换根 DP

Solution

设 $f_{u,d}$ 为与 $u$ 节点距离小于 $k$ 的权值和。

两边 dfs，第一遍向上转移，计算子树对当前节点的贡献。注意到与 $u$ 节点距离小于 $k$ 的节点数可以由它的左右子树转移而来，等价于其与所有子节点距离小于 $k-1$ 的节点数之和，得到 $f_{u,d}=\sum_{v\in \text{son}(u)} f_{v,d-1}$。

第二遍时计算父亲对当前节点的贡献。同样可以由一的思路 $f_{v,d}=f_{u,d-1}(v\in \text{son}(u))$，但是注意到这样会重复计算子树中一部分的节点，因为到 $u$ 距离为 $d$ 的点包含到 $v$ 距离为 $d-1$ 的点，如下图的 $f_{2,2}$ 就包含了 $f_{3,1}$ 的贡献，所以我们简单容斥一下减去 $f_{v,d-2}$ 的部分。

注意在进行第二遍 dfs 时，要注意循环顺序，防止容斥后的 $f$ 影响未更新的。

Core Code

void dfs1(int u, int fa) {
    for (auto v : e[u]) {
        if (v == fa) continue;
        dfs1(v, u);
        for (int d = 1; d <= k; d++) {
            f[u][d] += f[v][d-1];
        }
    }
}
void dfs2(int u, int fa) {
    for (auto v : e[u]) {
        if (v == fa) continue;
        for (int d = 1; d <= k; d++) {
            f[v][d] += f[u][d-1];
        }
        for (int d = k; d >= 2; d--) {
            f[v][d] -= f[v][d-2];
        }
        dfs2(v, u);
    }
}

CF474E Pillars

Link

• 给定序列长度为 $n$ 的序列 $a$，和 $d$。
• 找出一个最长的 $a$ 的子序列 $b$（设其长度为 $m$），使得对于任意的 $1\le i\lt m$，有 $|b_{i+1}-b_i|\ge d$。
• 输出 $m$ 和序列 $b$ 在序列 $a$ 中每个数的下标。

tag: 动态开点线段树, 线段树优化 DP

Solution

设 $f_i$ 表示前 $i$ 位的最大长度，可以得到一个显然的转移方程

$$\begin{aligned} f_i &= \max_{\lvert b_i - b_j\rvert \geq d}\{f_j\} + 1\\ &=\max_{1\leq j\leq a_i - d\ \text{or}\ a_i + d\leq j\leq n}\{f_j\} + 1 \end{aligned}$$

考虑线段树优化掉两部分区间最值。使用权值线段树，每次计算完 $i$ 后把 $f_i$ 放到对应的 $a_i$ 的位置即可。

数据范围过大，需动态开点或离散化。

Core Code

int n, d;
int tot = 0;
int rt;
struct pr {
    int val, id;
    bool operator < (pr const& x) {
        return val < x.val;
    }
}a[N], f[N], pre[N];
pr max(pr x, pr y) {
    if (x < y) return y;
    else return x;
}
struct node {
    pr val;
    int l, r;
}t[40 * N];
struct tree {
    void pushup(int p) {
        t[p].val = max(t[t[p].l].val, t[t[p].r].val);
    }
    void modify(int &p, int l, int r, int x, pr w) {
        if (!p) p = ++tot;
        if (l == r) {
            if (t[p].val < w) t[p].val = w;
            return;
        }
        int mid = (l + r) >> 1;
        if (x <= mid) modify(t[p].l, l, mid, x, w);
        else modify(t[p].r, mid + 1, r, x, w);
        pushup(p);
    }
    pr query(int p, int l, int r, int x, int y) {
        if (!p || y < x) return {0, 0};
        if (x <= l && r <= y) {
            return t[p].val;
        }
        int mid = (l + r) >> 1;
        pr res = {-INF, 0};
        if (x <= mid) res = max(res, query(t[p].l, l, mid, x, y));
        if (y >= mid + 1) res = max(res, query(t[p].r, mid + 1, r, x, y));
        return res;
    }
}sgt;
signed main() {
    n = read(); d = read();
    for (int i = 1; i <= n; i++) {
        a[i].val = read();
        a[i].id = i;
    }
    pr maxn = {0, 0};
    for (int i = 1; i <= n; i++) {
        f[i] = max(sgt.query(rt, 1, MAXN, 1, a[i].val - d),
                   sgt.query(rt, 1, MAXN, a[i].val + d, MAXN));
        bug(f[i].id);
        f[i].val += 1;
        maxn = max(maxn, {f[i].val, i});
        sgt.modify(rt, 1, MAXN, a[i].val, {f[i].val, i});
    }
    cout << maxn.val << endl;
    stack<int> st;
    for (int i = maxn.id; i >= 1; i = f[i].id) {
        bug(f[i].id);
        st.push(i);
    }
    while (!st.empty()) {
        cout << st.top() << " ";
        st.pop();
    }
    return 0;
}

CF708C Centroids

Link

给定一颗树，你有一次将树改造的机会，改造的意思是删去一条边，再加入一条边，保证改造后还是一棵树。

请问有多少点可以通过改造，成为这颗树的重心？（如果以某个点为根，每个子树的大小都不大于 $\dfrac{n}{2}$，则称某个点为重心）

tag: 树形 DP, 换根 DP

Solution

根据重心的定义，如果一个点 $u$ 不是重心，那么它的子树中一定有且仅有一个的 $siz > \lfloor\frac{n}{2}\rfloor$。如果想要把 $u$ 变成重心，那么就需要在这个子树中找到一个更小的子树，把它接到 $u$ 上，要解决的是是否存在一个这样的子树可以满足条件。

1. 如果先将一个不需要操作即可满足条件的节点钦定为根，那么这棵树的所有子树都满足 $siz\leq \lfloor\frac{n}{2}\rfloor$。
2. 所以，若在这棵新树上进行 DP，对于任何一个节点 $u$，如果它不是重心，只能因为除了它的子树以外的点数不满足要求，即 $n - siz_u$。我们记录一个 $g_u$ 表示除了 $u$ 子树以外的，不超过 $\lfloor\frac{n}{2}\rfloor$ 的最大子树大小，这个子树就是用来切下来挂到 $u$ 上的。
3. 那么，只需要判断除了上面这两部分一定合法的，剩下的那些点是否合法，即 $n - siz_u - g_u \leq \lfloor\frac{n}{2}\rfloor$ 是否成立。

也就是说，问题转化为求 $g_u$。

考虑自上而下转移，$g_u$ 可能来自于（$fa_u$ 的子树）/（$g_{fa_u}$）/（除了子树以外所有）。由于第一种情况，还要记录一个 $f_u$ 表示以 $u$ 为根的子树中，不超过 $\lfloor\frac{n}{2}\rfloor$ 的最大子树大小。我们还可以发现，在转移 $g_u$ 时，可能 $f_{fa_u}$ 就表示 $u$ 的子树，为了解决这种情况，需要记录最大值 $f_{u, 0}$ 和次大值 $f_{u, 1}$。

显然 $f_{u, 0}$ 需要自下而上转移：

$$f_{u, 0}= \begin{cases} f_{v, 0}, &\text{siz}_v >\lfloor\frac{n}{2}\rfloor\\ \text{siz}_u, &\text{siz}_v \leq\lfloor\frac{n}{2}\rfloor \end{cases}$$

可以按下面的 trick 维护次大值，为了表示方便，用 $x$ 表示需要被更新的数：

$$\begin{cases} f_{u, 1} = f_{u, 0}, f_{u, 0} = x, &f_{u, 0} < x\\ f_{u, 1} = x, &f_{u, 0}\leq x < f_{u, 1} \end{cases}$$

然后即可自上而下转移 $g_u$：

$$g_v=\max \begin{cases} f_{u, 1}, &f_{u, 0} = \text{siz}_v\\ f_{u, 0}, &f_{u, 0} \neq \text{siz}_v\\ g_u\\ n - \text{siz}_v, &n - \text{siz}_v \leq \lfloor\frac{n}{2}\rfloor \end{cases}$$

Core Code

void findrt(int u, int fa) {
    for (auto v : e[u]) {
        if (v == fa) continue;
        findrt(v, u);
        siz[u] += siz[v];
        if (siz[v] > n / 2) return;
    }
    if (n - siz[u] > n / 2) return;
    root = u;
}
void dfs1(int u, int fa) {
    for (auto v : e[u]) {
        if (v == fa) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if (siz[v] > n / 2) {
            if (f[v][0] > f[u][0]) {
                f[u][1] = f[u][0];
                f[u][0] = f[v][0];
            } else if (f[v][0] > f[u][1]) {
                f[u][1] = f[v][0];
            }
        } else {
            if (siz[v] > f[u][0]) {
                f[u][1] = f[u][0];
                f[u][0] = siz[v];
            } else if (siz[v] > f[u][1]) {
                f[u][1] = siz[v];
            }
        }
    }
}
void dfs2(int u, int fa) {
    for (auto v : e[u]) {
        if (v == fa) continue;
        g[v] = max(g[v], g[u]);
        if (n - siz[v] <= n / 2) {
            g[v] = max(g[v], n - siz[v]);
        }
        if (f[u][0] == siz[v]) {
            g[v] = max(g[v], f[u][1]);
        } else {
            g[v] = max(g[v], f[u][0]);
        }
        dfs2(v, u);
    }
    if (n - siz[u] - g[u] <= n / 2 || u == root) ans[u] = 1;
}
int main() {
    n = read();
    for (int i = 1; i < n; i++) {
        int u = read(), v = read();
        e[u].push_back(v);
        e[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) siz[i] = 1;
    findrt(1, 0);
    for (int i = 1; i <= n; i++) siz[i] = 1;
    dfs1(root, 0);
    dfs2(root, 0);
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << " ";
    }
    el;
}

AT_joi2015ho_b Cake 2

Link

$n$ 个数 $a_i$ 围成环，$A$ 和 $B$ 两人轮流取数，$A$ 先取，两人都将采取最优策略，求最大化 $A$ 取到的数的和。

tag: 区间 DP, 环

Solution

设 $f_{i, j}$ 表示剩余的蛋糕区间为 $[i, j]$ 时最大的答案，把 $a$ 断环为链。

考虑如何转移，由于两人轮流取，需要分类讨论：

1. 当前轮 $A$ 取，剩余区间为 $[l, r]$，显然一定满足的前提条件是 $\text{remain}\equiv n \pmod 2$，其中 $\text{remain}$ 表示的是剩余蛋糕区间长度（简单手玩即可得证）。此时，$A$ 可以取 $a_l$ 或 $a_r$，此时 $f_{l, r}=\max\{f_{l, r-1}+a_r, f_{l+1, r}+a_l\}$。
2. 当前轮 $B$ 取，变量定义同上，前提条件为 $\text{remain}$ 和 $n$ 奇偶性不同。此时 $B$ 一定取 $\max\{a_l, a_r\}$，那么留给 $A$ 的就是其中较小的一个。

所以有如下方程：

$$\text{len}\coloneqq l-r+1\\ f_{l, r}= \begin{cases} \max\{f_{l, r-1}+a_r, f_{l+1, r}+a_l\}, &\text{len}\equiv n \pmod 2\\ f_{l, r-1}, &a_l<a_r\ \text{and}\ \text{len}\not\equiv n \pmod 2\\ f_{l+1, r}, &a_l>a_r\ \text{and}\ \text{len}\not\equiv n \pmod 2 \end{cases}$$

最后考虑边界，如果最后一轮是 $A$ 取的，也就是 $n$ 为奇数时，对于任意长度为 $1$ 的区间 $[i, i]$，贡献都为 $a_i$；反之由 $B$ 取，那么贡献为 $0$。

Core Code

n = read();
for (int i = 1; i <= n; i++) {
    a[i] = read();
    a[i + n] = a[i];
}
a[0] = a[n];
if (n & 1) {
    for (int i = 1; i <= n * 2; i++) {
        f[i][i] = a[i];
    }
}
for (int len = 2; len <= n; len++) { // len := remain cakes
    for (int l = 1; l + len - 1 <= n * 2; l++) {
        int r = l + len - 1;
        if ((len & 1) == (n & 1)) { // JOI
            f[l][r] = max({f[l][r], f[l + 1][r] + a[l], f[l][r - 1] + a[r]});
        } else { // IOI
            if (a[l] < a[r]) f[l][r] = max(f[l][r], f[l][r - 1]);
            else f[l][r] = max(f[l][r], f[l + 1][r]);
        }
    }
}
int ans = 0;
for (int i = 1;i <= n; i++) {
    ans = max(ans, f[i][i + n - 1]);
}
cout << ans << endl;

P9759 [COCI2022-2023#3] Bomboni

Link

▶

题意

有 $n\times n$ 的方格。目前在左上角。通过向右或向下移动，要前往右下角。目前所在的格子没有障碍。

在每个格子中写了一个数字表示此地为糖果或障碍。Iva 会吃掉所有经过的糖果（包括起点和终点的糖果）并且将糖果对应的数字相乘。Iva 知道她自己最喜欢的数字是 $k$，所以她希望这个乘积结果能被 $k$ 整除。她想知道一共有多少条这样的路径。由于答案可能很大，她只想知道答案模 $998244353$ 的结果。

tag: trick

Solution

考虑从因数角度分析，发现只要一条路径上覆盖了 $k$ 的因数，这条路径就是合法的。

设 $f_{i, j, t}$ 为前 $(i, j)$ 位置时 $k$ 的因数剩余 $t$ 的路径数量。那么每次转移，从上一步去掉 $(i, j)$ 能贡献的因数，作为这次的答案。

最终答案即为 $f_{n, n, 1}$。

Core Code

f[1][1][k / __gcd(a[1][1], k)] = 1;
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        if (i - 1 >= 1 && a[i][j] != -1) {
            for (auto x : f[i - 1][j]) {
                int nw = x.first / __gcd(x.first, a[i][j]);
                f[i][j][nw] = (f[i][j][nw] + x.second + mod) % mod;
            }
        }
        if (j - 1 >= 1 && a[i][j] != -1) {
            for (auto x : f[i][j - 1]) {
                int nw = x.first / __gcd(x.first, a[i][j]);
                f[i][j][nw] = (f[i][j][nw] + x.second + mod) % mod;
            }
        }
    }
}

CF360B Levko and Array

Link

给定一个数列 $a$，可以对其中的元素做至多 $k$ 次修改，每次修改可以将数列中的一个数改成另一个。

求经过修改后，$\max\limits^n_{i=2}\left|a_i-a_{i-1}\right|$ 的最小值。

tag: 二分, trick

Solution

注意到答案具有单调性，二分答案 $x$。

考虑 check() 函数的写法，首先可以将题目中要求的最多 $k$ 次修改转化为至少保留 $n-k$ 个数。

不妨进行 DP，设 $f_i$ 表示前 $i$ 个数中在保留 $a_i$ 的情况下最多能保留的数量。两个数可以被保留，当且仅当 $\lvert a_j-a_i\rvert\leq (j-i)\times x$。这个比较好感性理解，两个位置 $(i,j)$ 之间有 $j-i+1$ 个数，也就意味着有 $j-i$ 个间隔，而这 $j-i$ 个间隔中每个间隔最大的符合条件的差是 $x$。

那么式子就很显然了：

$$f_i=\max_{1\leq j<i}\{f_j+1 \big| \lvert a_j-a_i\rvert\leq (j-i)\times x\}$$

Core Code

const int N = 2e3 + 10;
const int MAXN = 2e9;
int n, k;
int a[N];
int f[N];
bool check(int x) {
    for (int i = 1; i <= n; i++) f[i] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (abs(a[i] - a[j]) <= (i - j) * x) {
                f[i] = max(f[i], f[j] + 1);
            }
        }
        if (f[i] >= n - k) return 1;
    }
    return 0;
}
signed main() {
    n = read(); k = read();
    for (int i = 1; i <= n; i++) {
        a[i] = read();
    }
    int l = 0, r = MAXN;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
    return 0;
}

P4158 [SCOI2009] 粉刷匠

Link

有 $N$ 条木板需要被粉刷。每条木板被分为 $M$ 个格子。 每个格子要被刷成 $0/1$。每次粉刷只能选择一条木板上一段连续的格子，然后涂上一种颜色。每个格子最多只能被粉刷一次。只能粉刷 $T$ 次，他最多能正确粉刷多少格子？

tag: 背包

Solution

设 $f_{i,j}$ 表示前 $i$ 行刷 $j$ 次最多正确的格子数，发现这是一个背包，容易得到下面的转移：

$$f_{i,j}=\max_{1\leq k\leq j}\{f_{i-1,j-k}+g_{n, k}\}$$

其中，$g_{i, j}$ 表示当前行前 $i$ 格刷 $j$ 次最多正确的格子数。它可以在每次枚举行的时候更新，有转移：

$$g_{i,j}=\max_{0\leq l<i}\{g_{l, j-1}+h_{l+1,i}\}$$

其中，$h_{l, r}$ 表示当前行刷 $[l, r]$ 时刷一次最多刷对的格子数，也就是区间中 $0$ 和 $1$ 数量的最大值。

只需要在背包的转移前维护一下 $g$ 和 $h$ 即可。

Core Code

for (int i = 1; i <= n; i++) {
    memset(g, 0, sizeof(g));
    memset(maxn, 0, sizeof(maxn));
    for (int l = 1; l <= m; l++) {
        for (int r = l; r <= m; r++) {
            int cnt0 = 0, cnt1 = 0;
            for (int p = l; p <= r; p++) {
                if (s[i][p] == '0') cnt0++;
                else cnt1++;
            }
            maxn[l][r] = max(cnt0, cnt1);
        }
    }
    for (int j = 1; j <= m; j++) {
        for (int k = 1; k <= t; k++) {
            for (int l = 0; l < j; l++) {
                g[j][k] = max(g[j][k], g[l][k - 1] + maxn[l + 1][j]);
            }
        }
    }
    for (int j = t; j >= 1; j--) {
        for (int k = 1; k <= j; k++) {
            f[j] = max(f[j], f[j - k] + g[m][k]);
        }
    }
}

P1156 垃圾陷阱

Link

卡门掉进深度为 $D$ 英尺的垃圾井。她需要堆满垃圾，使垃圾高度 $\geq D$ 才能逃出。每个垃圾有扔下时间 $t$、堆放高度 $h$ 和食用后维持生命时间 $l$。卡门起始有 $10$ 小时的能量，$10$ 小时内若不进食将饿死。若体力为 0，吃垃圾或逃出井不会饿死。求卡门最早能逃出井的时间。

tag: 背包

Solution

看到两种选择，想到背包。用 $f_{i, j}$ 表示前 $i$ 个物品堆放高度为 $j$ 时的最大体力。

本题与普通 $0/1$ 背包不同的地方在于，本题有两种情况的成立条件和贡献不同，需要分类讨论：

1. 如果选择吃掉，那么 $f_{i,j}=f_{i-1,j}+l_i$。需要满足转移前一步剩余的体力能够等到当前垃圾扔下，即 $f_{i-1,j}\geq t_i$；
2. 如果选择不吃，那么 $f_{i,j}=f_{i-1,j-h_i}$。需要满足转移前一步剩余的体力能够等到当前垃圾仍下，即 $f_{i-1,j-h_i}\geq t_i\ (j\geq h_i)$。

需要特判 $h_i>d$ 的情况。

Core Code

memset(f, -INF, sizeof(f));
f[0] = 10;
d = read(), g = read();
for (int i = 1; i <= g; i++) {
    a[i].t = read(), a[i].f = read(), a[i].h = read();
    maxn = max(maxn, a[i].h);
}
sort(a + 1, a + g + 1);
for (int i = 1; i <= g; i++) {
    for (int j = max(d, maxn); j >= 0; j--) {
        if (f[j] >= a[i].t) {
            f[j] = max(f[j], f[j] + a[i].f);
        }
        if (j >= a[i].h && f[j - a[i].h] >= a[i].t) {
            f[j] = max(f[j], f[j - a[i].h]);
        }
    }
    if (d > maxn) {
        if (f[d] >= 0) {
            cout << a[i].t << endl;
            return 0;
        }
    } else {
        for (int j = d; j <= maxn; j++) {
            if (f[j] >= 0) {
                cout << a[i].t << endl;
                return 0;
            }
        }
    }
}

P1772 [ZJOI2006] 物流运输

Link

物流公司要把一批货物从码头 $1$ 运到码头 $n$。由于货物量比较大，需要 $t$ 天才能运完。货物运输过程中一般要转停好几个码头。

1. 每日会从 $1$ 港口发货；
2. 每日有可能会有港口封锁，封锁处不可走，需要换航线并加上换航线的成本。

tag: 最短路

Solution

首先想到可以对于每一天跑一遍最短路来预处理。

考虑 DP，设 $f_{i}$ 表示前 $i$ 天的最小成本。对于新的一天，有继续沿用之前的路线和走新的路线两种情况。所以设 $\text{minn}_{i, j}$ 表示 $i$ 到 $j$ 天走同一条路线的最短路径，显然可以对于每一个 $i, j$，跑一遍最短路预处理。此时有转移方程：

$$f_{i}=\max_{1\leq i<j}\{f_{j}+\text{minn}_{j+1, i}\times (i-j)+k\}$$

另外还有前 $i$ 天都走同一条路的情况，$f_{i}=\text{minn}_{1,i}\times i$。

Core Code

for (int i = 1; i <= d; i++) {
    p = read(), a = read(), b = read();
    for (int j = a; j <= b; j++) {
        block[p][j] = 1;
    }
}
for (int i = 1; i <= t; i++) {
    for (int j = i; j <= t; j++) {
        mp.reset();
        for (int p = 1; p <= n; p++) {
            for (int l = i; l <= j; l++) {
                if (block[p][l]) {
                    mp[p] = 1;
                    break;
                }
            }
        }
        minn[i][j] = dij();
    }
}
for (int i = 1; i <= t; i++) {
    f[i] = minn[1][i] * i;
}
for (int i = 1; i <= t; i++) {
    for (int j = 1; j < i; j++) {
        f[i] = min(f[i], f[j] + minn[j + 1][i] * (i - j) + k);
    }
}

P3174 [HAOI2009] 毛毛虫

Link

给定一颗 n 个节点的多叉树，找出包含分支最多的一条链，输出节点数。其中分支只计算与链直连的节点。

tag: 树形 DP, 树的直径

Solution

考虑从当前节点能控制的下一层节点入手，如果当前节点 $u$ 在链中，那么它所能控制的下一层节点数即为 $\text{deg}_u-1$，其中 $\text{deg}_u$ 表示 $u$ 的度。也就是说，可以按树的直径的思路，两遍 dfs，在递归的过程中统计答案。

注意需要考虑根节点没有父亲所带来的影响，和 $n=1$ 的特殊情况。

Core Code

void dfs(int u, int fa, int sum) {
    if (sum > maxd) {
        maxd = sum;
        maxpos = u;
    }
    for (auto v : e[u]) {
        if (v == fa) continue;
        dfs(v, u, sum + deg[u] - 1);
    }
}
int main() {
    n = read(), m = read();
    if (n == 1) {
        cout << 1 << endl;
        return 0;
    }
    for (int i = 1; i <= m; i++) {
        int u = read(), v = read();
        e[u].push_back(v);
        e[v].push_back(u);
        deg[u]++, deg[v]++;
    }
    dfs(1, 0, deg[1] - 1);
    maxd = 0;
    dfs(maxpos, 0, deg[maxpos] - 1);
    cout << maxd + 2 << '\n';
    return 0;
}

P1131 [ZJOI2007] 时态同步

Link

给定一颗 $n$ 个节点带边权的树，需要对于每颗子树调整根到叶子节点的路径
长度相等。每次操作可以对任意边权 $+1$。求最小操作次数。

tag: 树形 DP

Solution

要使操作次数最小，对于每个子树，就要操作根节点下的第一条边。所以从下向上递归更新答案，对于每个节点 $u$ 记录一个以 $u$ 为根的子树到叶节点的最大距离。遍历个儿子，累加缺少的距离。

Core Code

void dfs(int u, int fa) {
    for (auto x : e[u]) {
        int v = x.v, w = x.w;
        if (v == fa) continue;
        dfs(v, u);
        f[u] = max(f[u], f[v] + w);
    }
    for (auto x : e[u]) {
        int v = x.v, w = x.w;
        if (v == fa) continue;
        ans += f[u] - (f[v] + w);
    }
}

CF1324F Maximum White Subtree

Link

给定一棵 $n$ 个节点无根树，每个节点 $u$ 有一个颜色 $a_u$，若 $a_u$ 为 $0$ 则 $u$ 是黑点，若 $a_u$ 为 $1$ 则 $u$ 是白点。

对于每个节点 $u$，选出一个包含 $u$ 的连通子图，设子图中白点个数为 $cnt_1$，黑点个数为 $cnt_2$，请最大化 $cnt_1 - cnt_2$。并输出这个值。

tag: 换根 DP

Solution

记 $\text{color}_u$ 表示 $u$ 节点的颜色，黑白为 $-1/1$。

设 $f_u$ 表示以 $1$ 为根时 $u$ 子树的贡献。自下向上转移，容易得到

$$f_u=\text{color}_u+\sum_{v\in \text{son}(u)}\max\{0, f_{v}\}$$

考虑换根，设 $g_u$ 表示以 $u$ 为根时的答案，答案分为两部分：以 $u$ 为根的子树的贡献和剩余部分的贡献。第一部分显然为 $f_u$，第二部分可以通过父亲的答案转移，也就是 $g_{fa_u}-f_u$。通过前面的式子可以知道，如果 $f_u<0$，$f_u$ 不会被记录到 $f_{fa_u}$ 中，也就是说，$g_{fa_u}$ 的答案不包含 $f_u$。所以最终的式子

$$g_u=f_u+\max\{0, g_{fa_u}-\max\{0, f_u\}\}$$

Core Code

void dfs1(int u, int fa) {
    f[u] = a[u];
    for (auto v : e[u]) {
        if (v == fa) continue;
        dfs1(v, u);
        f[u] += max(0, f[v]);
    }
}
void dfs2(int u, int fa) {
    for (auto v : e[u]) {
        if (v == fa) continue;
        g[v] = f[v] + max(0, g[u] - max(0, f[v]));
        dfs2(v, u);
    }
}
g[1]=f[1]