动态规划刷题记录

Makerlife 的小站

2025-2026 赛季游记 && 退役记 NOIP 2024 游记集训记录 CSP2024 游记板子库杂题乱记数学期望学习笔记数论学习笔记 CF1000F One Occurrence 题解 P6878 [JOI 2020 Final] JJOOII 2 题解 CSP2023 游寄主定理 CF1695C Zero Path 题解字符串算法全家桶学习笔记 AT_ABC306D 题解 2023.06.03 模拟赛 Azure for Students 使用指北 AT_ABC286C 题解洛谷 AT1898 题解洛谷 CF1036A 题解洛谷 CF1040A 题解洛谷 SP3591 题解洛谷 AT278 题解洛谷 CF141B 题解洛谷 AT2561 题解洛谷 AT3525 题解洛谷 CF899B 题解洛谷 AT4787 题解洛谷 AT4810 题解洛谷 SP5450 题解

动态规划刷题记录

Makerlife · 2024-10-11 · via Makerlife 的小站

AT_DP_C Vacation

洛谷 Link

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

A：在海里游泳，获得幸福度 aia _ i。
B：在山上抓虫，获得幸福度 bib _ i。
C：在家做作业，获得幸福度 cic _ i。

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

Solution

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

则易得转移方程为：

fi,1=max⁡(fi−1,2,fi−1,3)fi,2=max⁡(fi−1,1,fi−1,3)fi,3=max⁡(fi−1,1,fi−1,2)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

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

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

从集合 AA 中选择一个元素 xx，从石堆中恰好移除 xx 个石子。

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

Solution

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

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

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

fi={1,aj≤i,fi−aj=00,otherwise.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

KK 颗糖分给 nn 个人，第 ii 个人至少分得 00 颗，至多分得 aia_i 颗，必须分完，求方案数，答案对 109+710^9+7 取模。

tag: 背包 DP, 前缀和

Solution

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

fi,j=∑k=max⁡(0,j−ai)jfi−1,kf_{i,j}=\sum^j_{k=\max(0,j-a_i)}f_{i-1,k}

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

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

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

fu,0=∏v∈u(fv,0+fv,1)fu,1=∏v∈ufv,0\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}

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

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

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

tag: 线段树优化 DP

Solution

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

fi=max⁡j=1i−1{fj∣hj<hi}+aif_{i}=\max_{j=1}^{i-1}\{f_{j}|h_j<h_i\}+a_{i}

考虑优化，观察到转移方程是区间最大值，想到用值域线段树优化。将 hih_i 作为线段树的下标，对应当前高度时的 fif_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

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

Solution

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

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

若小于前一个数，有 fi,j=∑k=ji−1fi−1,k\displaystyle f_{i,j}=\sum_{k=j}^{i-1}f_{i-1,k}。可以感性理解，由于前面一定有一个 rank 为 jj 的数，当前数扔进去的时候，相当于是扔到了原有排列（1∼i−11\sim i-1）中 rank 为 j−1j-1 和 jj 中间，所以说应该加上所有 rank 大于等于 jj 的贡献，即 j∼i−1j\sim i-1。

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

Core Code

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

AT_DP_W Intervals

Link

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

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

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

Solution

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

考虑 DP，设 fi,jf_{i,j} 表示前 ii 个位置中最后一个 11 的位置为 jj 的最大分数。

不难想到 fi,j=max⁡k=1jfi−1,k+∑lp≤k and rp=iap\displaystyle 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][l, r] 覆盖到 kk 位置。

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

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

fi,j={max⁡k=1j−1fi−1,k+∑rp=iap,i=jfi−1,j+∑lk≤j and rk=iak,i≠jf_{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}

滚动掉一维后，发现枚举位置 ii 时，如果 rj=ir_j=i，那么这段区间 [lj,rj][l_j, r_j] 会在 [lj,i][l_j, i] 中做出 aja_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

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

tag: 区间 DP

Solution

区间 DP，类似合并石子。

我们定义 fi,jf_{i,j} 记录 ii 到 jj 能删掉多少字符，显然最后答案应除以 33。

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

本题还需要特判一种特殊情况。如果 sis_i 和 sjs_j 为 i，sks_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

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

tag: 并查集

Solution

trick 题，记住。

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

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

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

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

fi=fi−1+fi−2f_i=f_{i-1}+f_{i-2}

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

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

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

所以可以得到：

fi=fi−1+k̸+fi−2−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

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

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

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

Solution

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

以 ff 为例，假设 sis_i 的所有值都是 +∞+\infty，可以得到显然的转移方程 fi=fi−1+1f_{i}=f_{i-1}+1。如果加上 sis_i 的限制条件，那么 fi=min⁡{fi−1+1,si}f_i=\min\{f_{i-1}+1, s_i\}。同理可得 gi=min⁡{gi+1+1,si}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

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

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

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

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

求公司的最小花费。

tag: DP

Solution

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

fi+1,x,y=min⁡(fi+1,x,y,fi,x,y+cz,qi+1)fi+1,x,z=min⁡(fi+1,x,z,fi,x,y+cy,qi+1)fi+1,y,z=min⁡(fi+1,y,z,fi,x,y+cx,qi+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}})

初值 q0=1,f0,2,3=0q_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

给定一个长度为 nn 的数列 aia_i，求 aia_i 的子序列 bib_i 的最长长度 kk，满足 bi and bi−1≠0b_i\ \text{and}\ b_{i-1} \neq 0，其中 2≤i≤k2\leq i\leq k。

tag: 位运算, DP

Solution

设 fif_{i} 表示最后一个数为 aia_i 的最长长度，biti\text{bit}_i 表示遍历到当前数二进制位 ii 为 11 的数量。

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

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

{fi=max⁡(fi,bitj)bitj=fi,ai and (1<<j)≠0\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

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

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

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

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

Solution

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

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

由此可得式子 fi=fi−1+fi−fi−1−2+2f_i=f_{i-1}+f_{i-f_{i-1}-2}+2。其中 i−fi−1−2i-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

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

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

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

fk,i,j={true,fk−1,i−lk,j=true or fk−1,i,j−lk=true or fk−1,i,j=truefalse,otherwise.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 背包一样，kk 这一维可以滚动掉。

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

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

tag: 树形 dp

Solution

树形 DP，设 fi,jf_{i,j} 为 ii 节点颜色 jj 的方案数。

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

从下向上转移：

{fu,1=∏v∈son(u)(fv,2+fv,3)fu,2=∏v∈son(u)(fv,1+fv,3)fu,3=∏v∈son(u)(fv,1+fv,2)\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

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

tag: 树形 DP

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

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

Solution

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

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

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

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

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

最终答案即为 min⁡(froot,1,froot,2)\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

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

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

如果 uu 选，那么他的儿子选不选并不重要，fu,0=∑v∈son(u)min⁡{fv,0,fv,1}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

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

tag: 树形 DP, 换根 DP

Solution

换根板子。

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

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

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

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

可以得到转移方程：

fv=fu−sizv×1+(n−sizv)×1=fu+n−2×sizvf_{v}=f_{u}-\text{siz}_{v}\times 1+(n-\text{siz}_{v})\times 1=f_u+n-2\times \text{siz}_v

其中 sizv×1\text{siz}_v\times 1 表示 44 的子树，n−sizvn-\text{siz}_v 表示 44 上面的点。

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

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

tag: 换根 DP

Solution

设 fu,df_{u,d} 为与 uu 节点距离小于 kk 的权值和。

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

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

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

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

给定序列长度为 nn 的序列 aa，和 dd。

找出一个最长的 aa 的子序列 bb（设其长度为 mm），使得对于任意的 1≤i<m1\le i\lt m，有 ∣bi+1−bi∣≥d|b_{i+1}-b_i|\ge d。

输出 mm 和序列 bb 在序列 aa 中每个数的下标。

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

Solution

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

fi=max⁡∣bi−bj∣≥d{fj}+1=max⁡1≤j≤ai−d or ai+d≤j≤n{fj}+1\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}

考虑线段树优化掉两部分区间最值。使用权值线段树，每次计算完 ii 后把 fif_i 放到对应的 aia_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

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

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

tag: 树形 DP, 换根 DP

Solution

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

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

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

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

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

fu,0={fv,0,sizv>⌊n2⌋sizu,sizv≤⌊n2⌋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 维护次大值，为了表示方便，用 xx 表示需要被更新的数：

{fu,1=fu,0,fu,0=x,fu,0<xfu,1=x,fu,0≤x<fu,1\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}

然后即可自上而下转移 gug_u：

gv=max⁡{fu,1,fu,0=sizvfu,0,fu,0≠sizvgun−sizv,n−sizv≤⌊n2⌋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

nn 个数 aia_i 围成环，AA 和 BB 两人轮流取数，AA 先取，两人都将采取最优策略，求最大化 AA 取到的数的和。

tag: 区间 DP, 环

Solution

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

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

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

所以有如下方程：

len≔l−r+1fl,r={max⁡{fl,r−1+ar,fl+1,r+al},len≡n(mod2)fl,r−1,al<ar and len≢n(mod2)fl+1,r,al>ar and len≢n(mod2)\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}

最后考虑边界，如果最后一轮是 AA 取的，也就是 nn 为奇数时，对于任意位置 ii，贡献都为 aia_i；反之由 BB 取，那么贡献为 00。

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×nn\times n 的方格。目前在左上角。通过向右或向下移动，要前往右下角。目前所在的格子没有障碍。

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

tag: trick

Solution

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

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

最终答案即为 fn,n,1f_{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

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

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

tag: 二分, trick

Solution

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

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

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

那么式子就很显然了：

fi=max⁡1≤j<i{fj+1∣∣aj−ai∣≤(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

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

tag: 背包

Solution

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

fi,j=max⁡1≤k≤j{fi−1,j−k+gn,k}f_{i,j}=\max_{1\leq k\leq j}\{f_{i-1,j-k}+g_{n, k}\}

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

gi,j=max⁡0≤l<i{gl,j−1+hl+1,i}g_{i,j}=\max_{0\leq l<i}\{g_{l, j-1}+h_{l+1,i}\}

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

只需要在背包的转移前维护一下 gg 和 hh 即可。

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

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

tag: 背包

Solution

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

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

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

需要特判 hi>dh_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

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

每日会从 11 港口发货；

每日有可能会有港口封锁，封锁处不可走，需要换航线并加上换航线的成本。

tag: 最短路

Solution

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

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

fi=max⁡1≤i<j{fj+minnj+1,i×(i−j)+k}f_{i}=\max_{1\leq i<j}\{f_{j}+\text{minn}_{j+1, i}\times (i-j)+k\}

另外还有前 ii 天都走同一条路的情况，fi=minn1,i×if_{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

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

tag: 树形 DP, 树的直径

Solution

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

注意需要考虑根节点没有父亲所带来的影响，和 n=1n=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

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

tag: 树形 DP

Solution

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

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

给定一棵 nn 个节点无根树，每个节点 uu 有一个颜色 aua_u，若 aua_u 为 00 则 uu 是黑点，若 aua_u 为 11 则 uu 是白点。

对于每个节点 uu，选出一个包含 uu 的连通子图，设子图中白点个数为 cnt1cnt_1，黑点个数为 cnt2cnt_2，请最大化 cnt1−cnt2cnt_1 - cnt_2。并输出这个值。

tag: 换根 DP

Solution

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

设 fuf_u 表示以 11 为根时 uu 子树的贡献。自下向上转移，容易得到

fu=coloru+∑v∈son(u)max⁡{0,fv}f_u=\text{color}_u+\sum_{v\in \text{son}(u)}\max\{0, f_{v}\}

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

gu=fu+max⁡{0,gfau−max⁡{0,fu}}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]

CF607B Zuma

Link

给定一个序列，每次可删除任意长度的回文子串，最小化将序列清空的删除次数。

tag: 区间 DP

Solution

设 fl,rf_{l,r} 表示清空 [l,r][l,r] 的最小操作次数。

最朴素的情况是枚举中间点，分成两部分来求，fl,r=min⁡{fl,i+fi+1,r}(i∈[l,r))f_{l,r}=\operatorname{min}\{f_{l,i}+f_{i+1,r}\}(i\in[l,r))。

当 al=ara_l=a_r 时，有另外的情况：

[l+1,r−1][l+1,r-1] 回文串，此时加上两端相等的值还是回文串；
[l+1,r−1][l+1, r-1] 不是回文串，此时内部随便删，删到内部只剩一个的时候，又可以与两端构成回文串。

所以 fl,r=min⁡{fl,r,fl+1,r−1}(al=ar)f_{l,r}=\operatorname{min}\{f_{l,r},f_{l+1,r-1}\}(a_l=a_r)。

两情况取最小值即可。

Core Code

memset(f, INF, sizeof(f));
for (int i = 1; i <= n; i++) {
    a[i] = read();
    f[i][i] = 1;
}
for (int len = 2; len <= n; len++) {
    for (int l = 1; l + len - 1 <= n; l++) {
        int r = l + len - 1;
        if (a[l] == a[r]) {
            if (len == 2) {
                f[l][r] = 1;
            } else {
                f[l][r] = f[l + 1][r - 1];
            }
        }
        for (int i = l; i < r; i++) {
            f[l][r] = min(f[l][r], f[l][i] + f[i + 1][r]);
        }
    }
}

P1896 [SCOI2005] 互不侵犯

Link

在 N×NN \times N 的棋盘里面放 KK 个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 88 个格子。

tag: 状压 DP

Solution

设 fi,S,jf_{i, S, j} 表示前 ii 行，当前行状态为 SS，棋盘已经安排了 jj 个国王的方案数。

首先看每行的约束条件，即若 xx 位置有国王，那么 x−1,x,x+1x-1, x, x+1 位置不能有国王。写为位运算形式即为 S&(S≪1)=0∧S&(S≫1)=0S \& (S \ll 1) = 0 \land S \& (S \gg 1) = 0

其次看行与行之间的约束条件，若 xx 位置有国王，那么上一行的 x−1,x,x+1x-1, x, x+1 位置不能有国王。若本行状态为 SS，上一行状态为 TT，则写为位运算形式为 S&(T≪1)=0∧S&T=0∧S&(T≫1)=0S \& (T \ll 1) = 0 \land S \& T = 0 \land S \& (T \gg 1) = 0。

最后，容易得到转移方程：

fi,S,j=∑Tfi−1,T,j−popcount(S)(S&(T≪1)=0∧S&T=0∧S&(T≫1)=0)f_{i, S, j} = \sum_{T} f_{i-1, T, j - \text{popcount}(S)} \quad (S \& (T \ll 1) = 0 \land S \& T = 0 \land S \& (T \gg 1) = 0)

Core Code

vector<vector<vector<int>>> f(n + 10, vector<vector<int>>((1 << n) + 10, vector<int>(k + 10, 0)));
f[0][0][0] = 1;
for (int i = 1; i <= n; i++) {
    for (int j = 0; j < (1 << n); j++) { // now
        if ((j & (j << 1)) || (j & (j >> 1))) continue;
        for (int l = 0; l < (1 << n); l++) { // last
            if ((l & (l << 1)) || (l & (l >> 1))) continue;
            if ((l & j) || (l & (j >> 1)) || (l & (j << 1))) continue;
            for (int cnt = __builtin_popcount(j); cnt <= k; cnt++) {
                f[i][j][cnt] += f[i - 1][l][cnt - __builtin_popcount(j)];
            }
        }
    }
}
for (int i = 0; i < (1 << n); i++) {
    ans += f[n][i][k];
}

P2014 [CTSC1997] 选课

Link

有 nn 门课程，每门课程有学分 sis_i，每门课程有零门或一门先修课，有先修课的课程需要先学完其先修课，才能学习该课程。

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

tag: 树上背包

Solution

首先可以将课程关系建树。发现如果 00 也算一个节点，那么这就是一棵以 00 为根的树。但这样会导致选择的课程数变成 m+1m+1。

设 fu,if_{u, i} 表示以 uu 为根的子树选择 ii 门课程时的最大学分数。对于每个儿子 vv，可以枚举从 vv 子树中选择 kk 门课程，那么有转移：

fu,i=max⁡0≤k<i{fu,i−k+fv,k}f_{u, i}=\max_{0\leq k<i}\{f_{u, i-k}+f_{v, k}\}

意思是从以 uu 为根的前半部分遍历过的子树中选择 i−ki-k 门课程，加上从 vv 为根的子树中选择 kk 门课程。注意由于如果要选择一个节点，那么它到根节点路径上的所有节点都必须被选择，也就是说父节点必须要被选，所以 kk 不能取到 ii。

Core Code

void dfs(int u, int m) {
    for (auto v : e[u]) {
        dfs(v, m);
        for (int i = m; i > 0; i--) {
            for (int k = 0; k < i; k++) {
                f[u][i] = max(f[u][i], f[u][i - k] + f[v][k]);
            }
        }
    }
}
int main() {
    int n = read(), m = read();
    for (int i = 1; i <= n; i++) {
        int k = read();
        f[i][1] = read();
        e[k].emplace_back(i);
    }
    dfs(0, m + 1);
    cout << f[0][m + 1] << '\n';
}

P3177 [HAOI2015] 树上染色

Link

有一棵点数为 nn 的树，树边有边权。给你一个在 0∼n0 \sim n 之内的正整数 kk ，你要在这棵树中选择 kk 个点，将其染成黑色，并将其他的 n−kn-k 个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间的距离的和的收益。问收益最大值是多少。

tag: 树上背包

Solution

可以发现，一条边 u,vu, v 经过的次数等于边的两侧同色点个数的乘积，即为：

contribu,v=j×(k−j)+(sizv−j)×(n−k−(sizv−j))\text{contrib}_{u,v}=j\times (k-j) + (\text{siz}_v-j) \times \left(n-k-\left(\text{siz}_v-j\right)\right)\\

其中，jj 表示以 vv 为根的子树中黑点的个数。

设 fu,if_{u, i} 表示以 uu 为根的子树中选择 ii 个黑点时的最大收益。那么有转移：

fu,j=max⁡j=max⁡(i−sizu+sizv)min⁡(i,sizv)(fu,i−j+fv,j+contribu,v×wi)f_{u,j}=\max_{j=\max(i-\text{siz}_u+\text{siz}_v)}^{\min(i, \text{siz}_v)}\left(f_{u,i-j}+f_{v,j}+\text{contrib}_{u,v}\times w_i\right)

这里 sizu\text{siz}_u 表示的是目前枚举到的 uu 子树的大小，注意限上下界防止复杂度退化，具体分析。

Core Code

auto dfs = [&](auto&& self, int u, int fa) -> void {
    siz[u] = 1;
    for (auto x : e[u]) {
        int v = x.v, w = x.w;
        if (v == fa) continue;
        self(self, v, u);
        siz[u] += siz[v];
        for (int i = min(k, siz[u]); i >= 0; i--) {
            for (int j = max(0ll, i - siz[u] + siz[v]); j <= min(i, siz[v]); j++) {
                int tot = j * (k - j) + (siz[v] - j) * (n - k - siz[v] + j);
                f[u][i] = max(f[u][i], f[u][i - j] + f[v][j] + w * tot);
            }
        }
    }

P10982 Connected Graph

Link

求 nn 个结点的有标号无向连通图个数，n≤1000n\leq 1000。

tag: 容斥, 计数

Solution

将题意转化为求有 nn 个节点的无向图总数减去不连通的无向图数量。

nn 个点的无向图总数显然为 2(n2)2^{\binom{n}{2}}。因为一个简单无向图最多有 (n2)\binom{n}{2} 条边，每条边可以选或不选。

考虑不连通的无向图数量。一个不连通的无向图可以分解为若干个连通块。我们可以枚举节点 11 所在的连通块大小为 jj，从剩余的 n−1n-1 个节点中选择 k−1k-1 个节点与节点 11 组成一个连通块，然后剩余的节点可以组合成任意的简单无向图。我们设 fif_i 表示 ii 个节点的连通图数量，则：

fi=2(i2)−∑j=1i−1(i−1j−1)×fj×2(i−j2)f_i=2^{\binom{i}{2}} - \sum_{j=1}^{i-1} \binom{i-1}{j-1}\times f_j\times 2^{\binom{i-j}{2}}

Core Code

for (int i = 1; i <= n; i++) {
    f[i] = ksm(2, i * (i - 1) / 2) % mod;
    for (int j = 1; j <= i - 1; j++) {
        f[i] = (f[i] - (c[i - 1][j - 1] * f[j] % mod) * ksm(2, (i - j) * (i - j - 1) / 2) % mod + mod) % mod;
    }
}

此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。原文来自 — 版权归原作者所有。

推荐订阅源

Makerlife 的小站

AT_DP_C Vacation

Solution

Core Code

AT_DP_K Stones

Solution

Core Code

AT_DP_M Candies

Solution

Core Code

AT_DP_P Independent Set

Solution

Core Code

AT_DP_Q Flowers

Solution

Core Code

AT_DP_T Permutation

Solution

Core Code

AT_DP_W Intervals

Solution

Core Code

TDPC_IWI イウィ

Solution

Core Code

ABC247F Cards

Solution

Core Code

ABC336D Pyramid

Solution

Core Code

SP703 Mobile Service

Solution

Core Code

P4310 绝世好题

Solution

Core Code

P1944 最长括号匹配

Solution

Core Code

P1284 三角形牧场

Solution

Core Code

P4084 [USACO17DEC] Barn Painting G

Solution

Core Code

P2458 [SDOI2006] 保安站岗

Solution

Core Code

P2016 战略游戏

Solution

Core Code

P3478 [POI2008] STA-Station

Solution

Core Code

P3047 [USACO12FEB] Nearby Cows G

Solution

Core Code

CF474E Pillars

Solution

Core Code

CF708C Centroids

Solution

Core Code

AT_joi2015ho_b Cake 2

Solution

Core Code

P9759 [COCI2022-2023#3] Bomboni

Solution

Core Code

CF360B Levko and Array

Solution

Core Code

P4158 [SCOI2009] 粉刷匠

Solution

Core Code

P1156 垃圾陷阱

Solution

Core Code