AtCoder Educational DP Contest 刷题记录

写在前面

深感自己 DP 很弱的 村人B 刷了点 DP 题，题集地址戳这里。

后记：刷完后感觉自己又行了

A - Frog 1

题意

给定 (n) 个石头，第 i 个石头的高度为 (h_i)。现在要求小青蛙从 1 号石头跳到 n 号石头，每次小青蛙可以选择从 i 号石头跳到 i+1 或 i+2 号石头，代价是起跳点与落点的高度差的绝对值。询问你最小代价。

解法

令 (f[i]) 表示小青蛙跳到第 (i) 号石头时的最小代价。

时间复杂度 (mathcal{O}(n))

代码

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n; cin >> n;
    vector<int> f(n, 0), h(n);
    for (auto &x : h) cin >> x;
    for (int i = 1; i < n; ++i) {
        f[i] = min(f[i - 1] + abs(h[i] - h[i - 1]),
                   i > 1 ? f[i - 2] + abs(h[i] - h[i - 2]) : INT_MAX);
    }
    cout << f[n - 1] << "
";
}

B - Frog 2

题意

给定 n 个石头与 k 的操作范围，第 i 个石头的高度为 hi。现在要求小青蛙从 1 号石头跳到 n 号石头，每次小青蛙可以选择从 i 号石头跳到 (i+s ( 1≤s≤k)) 号石头，代价是起跳点与落点的高度差的绝对值。询问你最小代价。

解法

令 (f[i]) 表示小青蛙跳到第 (i) 号石头时的最小代价。

时间复杂度 (O(nk))

代码

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    vector<int> f(n, 0), h(n);
    for (auto &x : h) cin >> x;
    for (int i = 1; i < n; ++i) {
        f[i] = INT_MAX;
        for (int j = 1; j <= k and (i - j) >= 0; ++j)
            f[i] = min(f[i], abs(h[i] - h[i - j]) + f[i - j]);
    }
    cout << f[n - 1] << "
";
}

C - Vacation

题意

给太郎的暑假时长为 n 天，每天他可以进行三种活动中的一种，每种活动给他带来的愉悦值各不相同。

如果当天进行过某一种活动，第二天即不能进行另一种活动，询问太郎能获得的最大愉悦值。

解法

令 (f[i][j]) 分别记录在第 i 天选做第 j 件娱乐活动的最大愉悦值。

时间复杂度 (O(n))

代码

const int N = 1e5 + 10;
int f[N][3], a[N][3], n;
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i)for (int j = 0; j < 3; ++j) cin >> a[i][j];
    for (int k = 1; k <= n; ++k)
        for (int i = 0; i < 3; ++i) for (int j = 0; j < 3; ++j)
                if (i != j) f[k][i] = max(f[k][i], f[k - 1][j] + a[k][j]);
    cout << max(f[n][0], max(f[n][1], f[n][2]));
}

D - Knapsack 1

题意

给定太郎拥有的 n 个物品，第 i 件物品大小为 wi 权重为 vi。

给定太郎的背包的最大容量 m，询问太郎能取得的最大权重和。

解法

01 背包求解。

f[i] 表示装总大小不超过 i 的物品后的最大权重和。

时间复杂度 (O(nm))

代码

const int N = 1e5 + 10;
ll f[N];
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for (int i = 1, w, v; i <= n; i += 1) {
        cin >> w >> v;
        for (int j = m; j >= w; j -= 1) f[j] = max(f[j], f[j - w] + v);
    }
    cout << f[m] << "
";
}

E - Knapsack 2 超大背包

题意

给定太郎拥有的 n 个物品，第 i 件物品大小为 (w_i) 权重为 (v_i)。

给定太郎的背包的最大容量 m，询问太郎能取得的最大权重和。

解法

发现权值不超过 100，令 f[i] 表示装填价值为 i 的物品的最小权值。

时间复杂度 (O(nv))

代码

const int N = 1e5 + 10;
ll f[N];
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    memset(f, 0x3f, sizeof(f)); f[0] = 0;
    int n, m;
    cin >> n >> m;
    for (int i = 1, w, v; i <= n; i += 1) {
        cin >> w >> v;
        for (int j = N - 1; j >= v; j -= 1) f[j] = min(f[j], f[j - v] + w);
    }
    int ans = N - 1;
    while (f[ans] > m) ans -= 1;
    cout << ans << '
';
}

F - LCS

题意

给定两个字符串 s 和 t，询问它们的任意一个最长公共子串。

解法

令 (dp[i][j]) 表示 s 的长度为 i 的前缀和 t 的长度为 j 的前缀的最长公共子串。

递归输出即可。

时间复杂度 (O(n))

代码

const int N = 3010;
char s[N], t[N];
int f[N][N], n, m;
void print(int x, int y) {
    if (!x || !y) return;
    if (s[x] == t[y]) {
        print(x - 1, y - 1);
        putchar(s[x]);
    } else {
        (f[x][y] == f[x][y - 1] ? y : x)--;
        print(x, y);
    }
}
int main() {
    scanf("%s%s", s + 1, t + 1);
    n = strlen(s + 1), m = strlen(t + 1);
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) {
            if (s[i] == t[j]) f[i][j] = f[i - 1][j - 1] + 1;
            f[i][j] = max(f[i][j], max(f[i - 1][j], f[i][j - 1]));
        }
    print(n, m);
}

G - Longest Path （DAG DP）

题意

给定一个 DAG（有向无环图），求其最长路径。

解法

按照 DFS 序 DP，f[i] 表示从 i 号点出发的最长路径上点的数量。

时间复杂度 (O(n))

代码

const int N = 1e5 + 10;
vector<int>e[N];
int f[N];
int dfs(int u) {
    if (f[u]) return f[u];
    for (int v : e[u]) if (v != u) f[u] = max(f[u], dfs(v));
    return ++f[u];
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m; cin >> n >> m;
    for (int i = 1, x, y; i <= m; ++i) {
        cin >> x >> y;
        e[x].push_back(y);
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) ans = max(ans, dfs(i));
    cout << ans - 1 << "
";
}

H - Grid 1

题意

给定一个 (n×m) 的网格，太郎起始在 ((1,1))，最终要到达 ((n,m))。每次太郎可以从 ((i,j)) 到达 ((i,j+1)) 或 ((i+1,j))，其中部分格子无法达到。

询问太郎的移动方案数。

解法

(f[i][j]) 表示从 ((1,1)) 出发到达 ((i,j)) 的移动方案。

时间复杂度 (O(nm))

代码

const int N = 1e3 + 10, mod = 1e9 + 7;
vector<string> vs(N);
int f[N][N];
int main() {
    int n, m;
    cin >> n >> m;
    f[0][0] = 1;
    for (int i = 0; i < n; ++i) cin >> vs[i];
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) {
            if (i == 0 and j == 0) continue;
            if (i >= 1 and vs[i - 1][j] == '.') f[i][j] += f[i - 1][j], f[i][j] %= mod;
            if (j >= 1 and vs[i][j - 1] == '.') f[i][j] += f[i][j - 1], f[i][j] %= mod;
        }
    cout << f[n - 1][m - 1];
}

I - Coins (最基本的概率DP)

题意

给定 (n) 个硬币，扔第 (i) 个硬币时，它正面朝上的概率为 (p_i)。

询问对每一个硬币扔一次，正面朝上的数量多余反面朝上的硬币的数量的概率。

保证 (n) 为奇数。

解法

定义 (f[i][j]) 表示前 i 个硬币中 j 个正面朝上的概率。

如果 (j = 0) 那么 (f[i][j] = f[i - 1][j] * (1 - p[i]))；

否则，(f[i][j] = f[i - 1][j - 1] * p[i] + dp[i - 1][j] * (1 - p[i]))

类似01背包的思路,当前这个状态我选还是不选.如果选,那么因为是 (j) 个朝上，所以要由前一枚硬币有 (j-1) 个朝上的状态转化而来,反之同理.

时间复杂度 (O(n^2))

代码

const int N = 3000;
double f[N][N] = {1}, p[N];
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> p[i];
        f[i][0] = f[i - 1][0] * (1 - p[i]);
        for (int j = 1; j <= i; ++j)
            f[i][j] = f[i - 1][j - 1] * p[i] + f[i - 1][j] * (1 - p[i]);
    }
    double ans = 0.0;
    for (int i = n / 2 + 1; i <= n; ++i) ans += f[n][i];
    cout << fixed << setprecision(10) << ans << "
";
}

J - Sushi （记忆化搜索DP）

题意

给定 (n) 盘寿司，每盘里有 (1) 到 (3) 个寿司。每次太郎随机选中一盘寿司，若该盘中有寿司，则吃掉一个。

询问你太郎的期望选择次数。

解法

看起来很像概率DP，但记忆化搜索即可。

(p[x][y][z]) 表示 x 盘 1 个寿司，y 盘 2 个寿司，z 盘 3 个寿司时的期望选择次数。

时间复杂度 (O(n^3))

代码

const int N = 310;
int num[4], n;
double p[N][N][N];
double P(int x, int y, int z) {
    if (p[x][y][z] >= 0)return p[x][y][z];
    double sum = (double) n / (x + y + z);
    if (x) sum += P(x - 1, y, z) * x / (x + y + z);
    if (y) sum += P(x + 1, y - 1, z) * y / (x + y + z);
    if (z) sum += P(x, y + 1, z - 1) * z / (x + y + z);
    return p[x][y][z] = sum;
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    memset(p, -1, sizeof(p)); // 初始化
    cin >> n;
    p[0][0][0] = 0;
    for (int i = 1, x; i <= n; ++i) cin >> x, num[x]++;
    cout << fixed << setprecision(10) << P(num[1], num[2], num[3]);
}

K - Stones

题意

给定一个集合 (A) 并给定一个石堆，包含 (k) 个石子。

太郎和次郎轮流进行博弈，太郎先行。每次他们可以选择集合 (A) 中的一个数字 (x)，并从该石堆中取走 (x) 个石子。

无法取走石子的人为输家，询问你赢家是谁。

解法

令 (dp[i]) 表示当前剩余 (i) 个石子时先手的胜败状态。

时间复杂度 (O(k))

代码

这道题很奇怪，在 1 100000 1 这组数据竟然会输出不出来，但又过了，懵逼ing.

const int N = 110, M = 100000 + 10;
int a[N], dp[M] = {-1}, n, k;
int check(int num) {
    if (dp[num]) return dp[num];
    bool f = false;
    for (int i = 1; !f and i <= n; i++)
        if (a[i] <= num && check(num - a[i]) == -1) f = true;
    return dp[num] = (f ? 1 : -1);
}
int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    cout << (check(k) == 1 ? "First" : "Second");
}

L - Deque （区间DP）

题意

给定一个序列 (a)，太郎和次郎轮流进行博弈，太郎先行。

每次可以从序列的两端中任取一端，删去那一段的第一个元素，并获取等量的分数。

太郎和次郎都希望能最大化自己与对面的得分差，询问你最终太郎与次郎的得分差。

解法

令 (dp[i][j]) 表示剩余区间为 ([i,j]) 时的最大得分差。

则下一次的人会选择 (max(a[l] - f[i+ 1][j],a[j] - f[i][j - 1]))

时间复杂度 (O(n^2))

代码

const int N = 3e3 + 10;
int a[N], n;
ll f[N][N];
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i], f[i][i] = a[i];
    for (int len = 1; len <= n; ++len)
        for (int i = 1; i + len <= n; ++i) {
            int j = len + i;
            f[i][j] = max(a[i] - f[i + 1][j], a[j] - f[i][j - 1]);
        }
    cout << f[1][n];
}

另外还可以写记忆化搜索

const ll N = 3e3 + 10, inf = 1e18;
ll a[N], f[N][N];
ll dfs(int l, int r) {
    if (l > r) return 0;
    if (f[l][r] != inf) return f[l][r];
    f[l][r] = max(a[l] - dfs(l + 1, r), a[r] - dfs(l, r - 1));
    return f[l][r];
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n; cin >> n;
    for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j) f[i][j] = inf;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    cout << dfs(1, n);
}

M - Candies

题意

给定 (n) 个小朋友的需求，第 (i) 个小朋友的需求为 (a_i)，表示他可以接受 ([0,a_i]) 个糖果。

给定 (m) 个糖果，要求你把这些糖果一个不剩的分配出去，询问你有多少种分配方案。

解法

(f[i][j]) 表示分配完前 (i) 个小朋友后还剩 (j) 个糖果的方案。

时间复杂度 (O(n^2))

代码

const int mod = 1e9 + 7, N = 110, M = 1e5 + 10;
int f[N][M], s[N][M];
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, k; cin >> n >> k;
    f[0][k] = s[0][k] = 1;
    for (int i = 1, x; i <= n; ++i) {
        cin >> x;
        for (int j = 1; j <= k; ++j)
            f[i][j] = (s[i - 1][min(k, j + x)] - s[i - 1][j - 1] + mod) % mod;
        s[i][0] = f[i][0] = s[i - 1][x];
        for (int j = 1; j <= k; ++j) s[i][j] = (s[i][j - 1] + f[i][j]) % mod;
    }
    cout << f[n][0];
}

N - Slimes

区间DP

题意

给定 n 个史莱姆，每个史莱姆的初始大小为 (a_i)。

这 n 个史莱姆站成一排。每次可以将相邻的两个史莱姆合并为一个，新的史莱姆大小为原来两个史莱姆的大小之和。合并的代价是新史莱姆的大小，询问将这 n 个史莱姆合并为 1 个的最小代价。

解法

(f[i][j]) 表示将区间 [i，j] 的史莱姆合并为 1 个史莱姆的最小代价。

时间复杂度 (O(n^3))

代码

const int N = 410;
ll f[N][N], s[N][N], a[N], n;
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    memset(f, 0x3f, sizeof(f));
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        f[i][i] = 0, s[i][i] = a[i];
    }
    for (int i = 1; i <= n; ++i) for (int j = i + 1; j <= n; ++j) s[i][j] = s[i][j - 1] + a[j];
    for (int len = 1; len < n; ++len)
        for (int i = 1; i + len <= n; ++i) {
            int j = i + len;
            for (int k = i; k < j; ++k)
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[i][j]);
        }
    cout << f[1][n];
}

另外一种写法(本质无区别)

void solve() {
    int n;
    cin >> n;
    vector<ll> v(n + 1), sum(n + 1);
    vector<vector<ll>> dp(n + 1, vector<ll>(n + 1));
    for (int i = 1; i <= n; i++) cin >> v[i], sum[i] = sum[i - 1] + v[i];
    for (int i = 1; i < n; i++)
        for (int j = 1; j + i <= n; j++) {
            dp[j][j + i] = 1e18;
            for (int k = j; k < j + i; k++)
                dp[j][j + i] = min(dp[j][j + i], dp[j][k] + dp[k + 1][j + i]);
            dp[j][j + i] += sum[j + i] - sum[j - 1];
        }
    cout << dp[1][n] << '
';
}

O - Matching 状压DP

题意

给定 n 男 n 女，以及任意一对男女之间是否匹配。

询问有多少种方法将这男女完全配对。

解法

令 num(i) 表示 i 的二进制展开中 1 的数量。

f[i] 表示前 num(i) 个男生与状态为 i 的女生配对的方案数。

时间复杂度 (O(2n×n))

代码

const int N = 22, mod = 1e9 + 7;
int a[N][N], f[1 << N] = {1}, n;
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) cin >> a[i][j];
    for (int s = 0; s < (1 << n); ++s) {
        int i = __builtin_popcount(s);
        for (int j = 1; j <= n; ++j)
            if (s & (1 << (j - 1)) && a[i][j])
                f[s] = (f[s] + f[s ^ (1 << (j - 1))]) % mod;
    }
    cout << f[(1 << n) - 1];
}

P - Independent Set 树形DP

题意

给定一颗树，可以把树上的每一个节点染色为黑色或白色，但不允许两个相邻的节点同时为黑色。

询问染色方案数。

解法

挺基础的树形DP，

令 (f1[i]) 表示 (i) 为白色时以 (i) 为根节点的子树的染色方案。

令 (f2[i]) 表示 (i) 为黑色时以 (i) 为根节点的子树的染色方案。

时间复杂度 (mathcal{O}(n))

代码

const int N = 1e5 + 10, mod = 1e9 + 7;
vector<int>e[N];
ll f1[N], f2[N], n;
void dfs(int u, int f) {
    f1[u] = f2[u] = 1;
    for (int v : e[u]) {
        if (f == v) continue;
        dfs(v, u);
        f1[u] = f1[u] * (f1[v] + f2[v]) % mod;
        f2[u] = f2[u] * f1[v] % mod;
    }
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    for (int i = 1, x, y; i < n; ++i) {
        cin >> x >> y;
        e[x].push_back(y), e[y].push_back(x);
    }
    dfs(1, 0);
    cout << (f1[1] + f2[1]) % mod;
}

Q - Flowers （LCS + 树状数组优化）

题意

(n) 支花，第 (i) 支花的高为 (w[i])，价值为 (v[i]) ，其中每支花的高度都不相同，范围在 (1) 到 (n)。求从给定的花的序列中找到一段高度递增的子序列，求这段子序列的价值最大值。

解法

建立数组 (dp) ，(dp[i]) 为取第朵花时的最大价值,在求要第支花时的最大值时,要找到他前边比他矮的花的价值最大值，然后 (dp[i]=dp[j]+v[i]) .

在找 (dp[j]) 时,不能遍历。因为高度在 (1-n) 这个范围 所以可以建立一个树状数组来存储前个花的价值,这样就可以在 (log m) 的时间内求出前支花中高度在 (1 -(w[i]-1)) 的价值的最大值

代码

const int N  = 1e6 + 10, mod = 1e9 + 7;
ll n, f[N], h[N], a[N];
ll tr[N]; // 树状数组
int lowbit(int x) {return x & (-x);}
void update(int x, ll val) { for (; x <= n; x += lowbit(x)) tr[x] = max(tr[x], val);}
ll query(ll x) {
    ll ans = 0;
    for (; x > 0; x -= lowbit(x)) ans = max(ans, tr[x]);
    return ans;
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> h[i];
    for (int i = 1; i <= n; ++i) cin >> a[i];
    ll cnt = 0;
    for (int i = 1; i <= n; ++i) {
        f[i] = a[i] + query(h[i]);
        cnt = max(cnt, f[i]);
        update(h[i], f[i]);
    }
    cout << cnt << "
";
}

R - Walk (矩阵快速幂)

题意

给定一个 n 个节点的有向图的邻接矩阵，求该有向图中长度为 k 的路径长。

解法

算法涉及：倍增 Floyd

答案为该邻接矩阵的 (k) 次幂的行列式。

学过离散数学的后面图论的话大概都知道求有向图中长度为 (k) 的路径长的路径与原始图的 (k) 次方相关，所以只需要求原矩阵的 (k) 次幂即可

使用矩阵快速幂即可，时间复杂度 (mathcal{O}(n^2log k))

代码

const int mod = 1e9 + 7;
ll n, k;
struct Matrix {
    ll mat[50][50];
    void clear() {memset(mat, 0, sizeof(mat));}
    void reset(int n) {
        clear();
        for (int i = 0; i < n; ++i) mat[i][i] = 1;
    }
} a;
Matrix MatrixMul(Matrix a, Matrix b) { // 矩阵快速乘
    Matrix t; t.clear();
    for (int i = 0; i < n; ++i)
        for (int k = 0; k < n; ++k)
            for (int j = 0; j < n; ++j)
                t.mat[i][j] = (t.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % mod;
    return t;
}
ll MatrixQpow(Matrix a, ll p) { // 矩阵快速幂
    Matrix s; s.reset(n);
    for (; p; p >>= 1, a = MatrixMul(a, a))
        if (p & 1) s = MatrixMul(s, a);
    ll sum = 0;
    for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j)
            sum = (sum + s.mat[i][j]) % mod;
    return sum;
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> k;
    for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) cin >> a.mat[i][j];
    cout << MatrixQpow(a, k);
}

S - Digit Sum 数位DP

题意

给定一个数字 n 与数字 d，询问你 1 到 n 中多少数的数位和为 d 的倍数。

解法

数位 DP 即可，(f[i][j]) 表示 (i) 位数中，前缀对 d 取模为 j 的情况下的数位和为 d 的倍数的数的数量。

令 (m) 表示 (n) 的位数，时间复杂度 (O(md))

思路参考：Here

代码

const int N = 1e4 + 10, mod = 1e9 + 7;
char c[N];
int d, n, a[N];
ll f[N][101];
ll dfs(int len, int pre, int top) {
    if (!len) return pre == 0;
    if (!top && f[len][pre] != -1) return f[len][pre];
    int up = top ? a[len] : 9;
    ll num = 0;
    for (int i = 0; i <= up; ++i)
        num = (num + dfs(len - 1, (pre + i) % d, top && (i == up))) % mod;
    if (!top) f[len][pre] = num;
    return num;
}
int main() {
    memset(f, -1, sizeof(f));
    scanf("%s%d", c + 1, &d);
    n = strlen(c + 1);
    for (int i = n, j = 1; i; i--, j++) a[j] = c[i] - '0';
    cout << (dfs(n, 0, 1) - 1 + mod) % mod;
}

T - Permutation

题意

给定一个长度为 (n−1) 的仅包含 < 和 > 的字符串，第 (i) 位字符表示 (a[i]) 与 (a[i+1]) 的大小关系。

询问能构造多少长度为 (n) 的，满足该字符串的要求，且恰好包含 (1) 到 (n) 每个数一次的序列。

解法

(f[i][j]) 表示安排完前 (i) 个数且第 (i) 个数为 (j)​ 的方案数。

时间复杂度 (O(n^2))

代码

const int N = 3e3 + 10, mod = 1e9 + 7;
int f[N][N], n;
char c[N];
int main() {
    scanf("%d%s", &n, c + 1);
    f[1][1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (c[i - 1] == '<')
            for (int j = 2; j <= i; ++j) f[i][j] = (f[i][j - 1] + f[i - 1][j - 1]) % mod;
        else
            for (int j = i - 1; j; --j) f[i][j] = (f[i][j + 1] + f[i - 1][j]) % mod;
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) ans = (ans + f[n][i]) % mod;
    cout << ans;
}

U - Grouping(状压DP)

题意

给定 n 个兔子之间的匹配程度，太郎想要把这 n 只兔子分组，对于任意两只分到同一组的兔子，太郎将会获得它们两对应的匹配程度的得分。

询问太郎的最大得分。

解法

令 (sum[i]) 表示状态为 (i) 的兔子分为一组时的得分。

(f[i]) 表示将状态为 (i) 的兔子分好组的最大得分。

时间复杂度 (O(2^{n}×n))

代码

const int N = 17, M = 65536;
int a[N][N], v[N], n;
ll f[M], sum[M];
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) cin >> a[i][j];
    for (int t = 0; t < (1 << n); ++t) {
        int num = 0;
        for (int i = 0; i < n; ++i)
            if (t >> i & 1ll) v[num++] = i;
        ll s = 0;
        for (int i = 0; i < num; ++i) for (int j = i + 1; j < num; ++j) s += a[v[i]][v[j]];
        f[t] = sum[t] = s;
    }
    for (int i = 0; i < (1 << n); ++i) for (int j = i; j; j = (j - 1) & i) f[i] = max(f[i], f[i ^ j] + sum[j]);
    cout << f[(1 << n) - 1];
}

V - Subtree (树形DP)

题意

给定一颗 n 个节点的树，将其每个节点染成黑色或白色，要求任意两个黑色节点之间的路径上无白色节点。

询问对于每一个节点，若它为黑色，则有多少染色方案数。

解法

考虑到模数可能为合数，因此无法用乘法逆元，对每一个节点单独计算它的子树的前缀乘积与后缀乘积。

s1[i] 表示 i 号节点为黑色时，它的子树节点的染色方案。

s2[i] 表示 i 号节点为黑色时，非它的子树节点的染色方案。

时间复杂度 (O(n))

代码

const int N = 1e5 + 10;
vector<int>e[N];
vector<ll>a[N], b[N];
ll f[N], len[N], m;
ll s1[N], s2[N] = {0, 1};
void dfs1(int u) {
    e[u].erase(remove(e[u].begin(), e[u].end(), f[u]), e[u].end());
    len[u] = e[u].size() - 1;
    a[u].resize(len[u] + 1), b[u].resize(len[u] + 1);
    ll sa = 1, sb = 1;
    for (int i = 1; i <= len[u]; ++i) {
        f[e[u][i]] = u;
        dfs1(e[u][i]);
        a[u][i] = sa = sa * (s1[e[u][i]] + 1) % m;
    }
    for (int i = len[u]; i; --i) b[u][i] = sb = sb * (s1[e[u][i]] + 1) % m;
    s1[u] = sa;
}
void dfs2(int u) {
    for (int i = 1; i <= len[u]; i++) {
        s2[e[u][i]] = s2[u];
        if (i > 1) s2[e[u][i]] = s2[e[u][i]] * a[u][i - 1] % m;
        if (i < len[u]) s2[e[u][i]] = s2[e[u][i]] * b[u][i + 1] % m;
        s2[e[u][i]]++;
        dfs2(e[u][i]);
    }
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n; cin >> n >> m;
    for (int i = 1; i <= n; ++i) e[i].push_back(-1);
    for (int i = 1, x, y; i < n; ++i) {
        cin >> x >> y;
        e[x].push_back(y), e[y].push_back(x);
    }
    dfs1(1), dfs2(1);
    for (int i = 1; i <= n; ++i) cout << s1[i] * s2[i] % m << "
";
}

W - Intervals 线段树优化

题意

给定 m 个区间 [1,n] 的子区间。要求你构造出一个长度为 n 且只包含 0 和 1 的字符串，使得得分尽可能大。询问你最大得分。

得分计算方式为：若该字符串中第 i 位为 1 ，那么得分加上所有包括 i 的区间对应的权值。

解法

令 f[i] 表示安排完前 i 位，且第 i 位为 1 时的最大值。线段树优化转移。

后来发现无需存储 f[i]，只需区间加值与维护全局最值的线段树即可。

时间复杂度 (O(nlog ⁡n))

代码

const int N = 2e5 + 10;
ll s[N << 2], t[N << 2];
vector<pair<int, int>> a[N];
void add(int x, int L, int R, int l, int r, ll c) {
    if (l <= L && R <= r) return (void)(s[x] += c, t[x] += c);
    int mid = (L + R) >> 1;
    if (l <= mid) add(x << 1, L, mid, l, r, c);
    if (r > mid) add(x << 1 | 1, mid + 1, R, l, r, c);
    s[x] = max(s[x << 1], s[x << 1 | 1]) + t[x];
}
int n, m;
int main() {
    cin >> n >> m;
    for (int i = 1, x, y, z; i <= m; i++) {
        cin >> x >> y >> z;
        a[y].emplace_back(x, z);
    }
    for (int i = 1; i <= n; i++) {
        add(1, 1, n, i, i, s[1]);
        for (auto &it : a[i]) add(1, 1, n, it.first, i, it.second);
    }
	cout << max(s[1],0ll) << "
";
    return 0;
}

X - Tower

题意

给定 n 个方块，每个方块有三个属性：重量 w 、强度 s 与价值 v。

太郎想要选择价值总和尽可能大的一些方块摞在一起，但是每个方块上方的方块的总质量不能超过该方块的强度。

询问太郎能取得的最大价值。

解法

容易发现从上向下放更容易考虑，于是首先应该放承重能力差且重量小的方块在上面，但是这种关系仅是一种偏序关系，需要拓展为全序关系。

假定现在已经堆叠了重量为 W 的方块，在下面要放下 i 与 j 两个方块，且最佳策略是 i 在上。那么有

(s_i<W+w_j)

(s_j≥W+w_i)

化简得

(s_i+w_i<s_j+w_j)

这样就确定了对于任意两个物品的上下位置的全序关系了。

问题化简为简单的背包，时间复杂度 (O(n(w+s+log⁡n)))

代码

const int N = 1010,M = 20010;
struct faner {int w, s, v;} a[N];
ll f[M], ans;
bool cmp(faner a, faner b) { return a.s + a.w < b.s + b.w; }
int main() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) scanf("%d%d%d", &a[i].w, &a[i].s, &a[i].v);
    sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; i++) for (int j = M - 1; j >= a[i].w; j--)
            if (a[i].s + a[i].w >= j) f[j] = max(f[j], f[j - a[i].w] + a[i].v);
    for (int i = 1; i < M; i++) ans = max(ans, f[i]);
    cout << ans << '
';
    return 0;
}

Y - Grid 2

题意

给定一个网格的高度 n 与宽度 m，与网格中的 k 个障碍。太郎起始在 (1,1)，最终要到达 (n,m)。每次太郎可以从 (i,j) 到达 (i,j+1) 或 (i+1,j)。其中障碍格子无法达到。

询问太郎的移动方案数。

解法

容斥原理，用无障碍情况下的方案数减去经过障碍的方案数即可。

时间复杂度 O(n+m+k2)

代码

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long
#define N 200001
int n, m, num;
ll f[N] = {1}, fac[N] = {1}, ifac[N] = {1}, inv[N] = {1, 1};
ll Calc(int n, int k) { return fac[n] * ifac[k] % mod * ifac[n - k] % mod; }
struct faner {
    int x, y;
} a[N] = {1, 1};
bool cmp(faner a, faner b) { return a.x == b.x ? a.y < b.y : a.x < b.x; }
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 2; i <= n + m; i++)
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    for (int i = 1; i <= n + m; i++)
        fac[i] = fac[i - 1] * i % mod, ifac[i] = ifac[i - 1] * inv[i] % mod;
    scanf("%d", &num);
    for (int i = 1; i <= num; i++) scanf("%d%d", &a[i].x, &a[i].y);
    sort(a + 1, a + 1 + num, cmp);
    a[++num] = {n, m};
    for (int i = 0; i < num; i++) {
        for (int j = i + 1; j <= num; j++) {
            if (a[i].y > a[j].y) continue;
            ll sum = Calc(a[j].x - a[i].x + a[j].y - a[i].y, a[j].x - a[i].x);
            f[j] = (mod + f[j] - f[i] * sum % mod) % mod;
        }
    }
    printf("%lld
", (mod - f[num]) % mod);
    return 0;
}

Z - Frog 3 单调队列优化DP

题意

给定 (n)​​​ 个石头，第 (i)​​ 个石头的高度为 (h_i)​​。现在要求小青蛙从 (1)​​ 号石头跳到 n 号石头，每次小青蛙可以选择从 $i $​​号石头跳到 (i+s ( 1≤s≤n−i )) 号石头，代价是起跳点与落点的高度差的平方加上一个常数 (C)。询问你最小代价。

解法

可以发现当高差过大时，采取中间跳板会使策略更优，高差小时则应当直接跳。

于是维护一个单调队列，保存多个跳板，每次取最优策略即可。

时间复杂度 (mathcal{O}(n))

代码

#define N 200001
ll q[N] = {0, 1}, f[N], h[N], n, c;
double slope(int i, int j) {
    return (f[i] - f[j] + h[i] * h[i] - h[j] * h[j]) / 2.0 / (h[i] - h[j]);
}
main() {
    scanf("%lld%lld", &n, &c);
    for (int i = 1; i <= n; i++) scanf("%lld", &h[i]);
    int l = 1, r = 1;
    for (int i = 2; i <= n; i++) {
        while (l < r && slope(q[l], q[l + 1]) <= h[i]) l++;
        f[i] = f[q[l]] + (h[i] - h[q[l]]) * (h[i] - h[q[l]]) + c;
        while (l < r && slope(q[r - 1], q[r]) >= slope(q[r], i)) r--;
        q[++r] = i;
    }
    printf("%lld
", f[n]);
    return 0;
}

评价

AtCoder的这套 DP 题知识点涵盖广泛，题面描述清晰，题目质量很高，很值得入门选手尝试。QAQ