动态规划 刷题记录

tag: 背包 DP, 前缀和

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

类似背包的处理思路，设 $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$ 值。

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

tag: 树形 DP

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

设 $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$ 号点为根，输入无序需建双向边。

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

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

tag: 线段树优化 DP

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

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

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

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

有一个长为 $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$ 的方案数。

由于 $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}$ 。

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

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;
}

TDPC_IWI イウィ

洛谷 link

tag: 区间 DP

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

区间 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

并查集，待填坑。

ABC336D Pyramid

▶

题意

对于正整数 $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$ 是多少。

显然一个金字塔数列是由左右两部分拼接而成的。设 $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\}$ 。

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

▶

题意

有 $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} \not =0 $，其中 $2\leq i\leq k$ 。

tag: 位运算, DP

Solution

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

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

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

\begin{cases} f_i&=\max(f_i, bit_j)\\ bit_j&=f_i \end{cases} , a_i\ \text{and}\ (1<<j)\not =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 最长括号匹配

▶

题意

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

(),[] 是括号匹配的字符串。
若 A 是括号匹配的串，则 (A),[A] 是括号匹配的字符串。
若 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 三角形牧场

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

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}\ \texttt{或}\ f_{k-1,i,j-l_k}=\text{true}\ \texttt{或}\ 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

给定一颗 $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 son(u)} (f_{v,2}+f_{v,3})\\ f_{u,2}=\prod_{v\in son(u)} (f_{v,1}+f_{v,3})\\ f_{u,3}=\prod_{v\in 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] 保安站岗

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

tag: 树形 DP

Solution

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

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

首先第一种情况显然 $f_{u,1}=\sum_{v\in 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 son(u)}\min(f_{v,1}, f_{v,2})$ 。

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

最终答案即为 $\min(f_{root,1}, f_{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;
}

P3478 [POI2008] STA-Station

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

tag: 树形 DP, 换根 DP

Solution

换根板子。

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

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

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

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

可以得到转移方程：

f_{v}=f_{u}-siz_{v}\times 1+(n-siz_{v})\times 1=f_u+n-2\times siz_v

其中 $siz_v\times 1$ 表示 $4$ 的子树， $n-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

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

tag: 换根 DP

Solution

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

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

第二遍时计算父亲对当前节点的贡献。同样可以由一的思路 $f_{v,d}=f_{u,d-1}(v\in 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

给定序列长度为 $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