《信息学奥赛一本通·高手专项训练》集训 Day 12

luckydrawbox · 2022-08-12 08:23:45 · 个人记录

背包问题

\color{Green}100\color{Black}+\color{Green}100\color{Black}+\color{Green}100\color{Black}=\color{Green}300\color{Black}/\color{Gold}\text{Rank 1}

\color{#3498DB}\text{A. 消失之物}

题目

ftiasch 有 n 个物品, 体积分别是 w_1,w_2,\dots,w_n。由于她的疏忽，第 i 个物品丢失了。

“要使用剩下的 n-1 物品装满容积为 x 的背包，有几种方法呢？”——这是经典的问题了。

她把答案记为 \text{cnt}(i,x) ，想要得到所有i \in [1,n], x \in [1,m] 的 \text{cnt}(i,x) 表格。

题解

P4141 消失之物

先进行普通的背包，设 dp_{i,j} 表示前 i 个物品填满容积为 j 的背包的方案数，那么 dp_{i,0}=1,dp_{i,j}\leftarrow dp_{i-1,j-w_i}。第一维可以直接优化掉，别忘了 j 要倒序枚举 m\rightarrow w_i：

dp_j=dp_j+dp_{j-w_i}

但是有一个物品是要消失的，我们考虑如何去掉一个物品对背包的影响，其实只要把加上的 dp_{j-w_i} 减去即可，由于是倒序加的，所以反过来必须正序 w_i\rightarrow m 减。

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;
long long read() {
    long long x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
void write(long long x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const int N = 2010;
int n, m, w[N];
ll dp[N], f[N];
int main() {
    n = read();
    m = read();
    for (int i = 1; i <= n; i++) w[i] = read();
    dp[0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= w[i]; j--) dp[j] = (dp[j] + dp[j - w[i]]) % 10;
    for (int i = 1; i <= n; i++) {
        memcpy(f, dp, sizeof(f));
        for (int j = w[i]; j <= m; j++) f[j] = ((f[j] - f[j - w[i]]) % 10 + 10) % 10;
        for (int j = 1; j <= m; j++) write(f[j]);
        putchar('\n');
    }
    return 0;
}

\color{#3498DB}\text{B. 排兵布阵}

题目

小 C 正在玩一款排兵布阵的游戏。在游戏中有 n 座城堡，每局对战由两名玩家来争夺这些城堡。每名玩家有 m 名士兵，可以向第 i 座城堡派遣 a_i 名士兵去争夺这个城堡，使得总士兵数不超过 m。

如果一名玩家向第 i 座城堡派遣的士兵数严格大于对手派遣士兵数的两倍，那么这名玩家就占领了这座城堡，获得 i 分。

现在小 C 即将和其他 s 名玩家两两对战，这 s 场对决的派遣士兵方案必须相同。小 C 通过某些途径得知了其他 s 名玩家即将使用的策略，他想知道他应该使用什么策略来最大化自己的总分。

由于答案可能不唯一，你只需要输出小 C 总分的最大值。

题解

P5322 [BJOI2019] 排兵布阵

将第 i 个城堡的 a_i 排序，记为 a_{i,1},a_{i,2}……a_{i,s}，这样小 C 若往这个城堡排 2\times a_{i,j}+1 名士兵，则能获得 i\times j 分。

这样，我们的问题就变成了有 n 组物品，每组物品有 s 个且只能选一个，第 i 组第 j 个背包的体积为 2\times a_{i,j}+1，价值为 i\times j，求装进容积为 m 的背包的最大价值。直接背包即可。

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;
long long read() {
    long long x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
void write(long long x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const int N = 110, M = 2e4 + 10;
int s, n, m, dp[M], ans;
vector<int> a[N];
int main() {
    s = read();
    n = read();
    m = read();
    for (int i = 1; i <= s; i++) {
        for (int j = 1; j <= n; j++) {
            a[j].push_back(read());
        }
    }
    for (int i = 1; i <= n; i++) sort(a[i].begin(), a[i].end());
    for (int i = 1; i <= n; i++) {
        for (int k = m; k >= 0; k--)
            for (int j = 0; j < a[i].size(); j++)
                if (k >= a[i][j] * 2 + 1)
                    dp[k] = max(dp[k], dp[k - a[i][j] * 2 - 1] + (j + 1) * i);
    }
    for (int i = 0; i <= m; i++) ans = max(ans, dp[i]);
    write(ans);
    return 0;
}

\color{#3498DB}\text{C. 多人背包}

题目

小泽和好朋友们要去爬山啦！

他们一共有 K 个人，每个人都会背一个包。这些包的容量是相同的，都是 V。可以装进背包里的一共有 N 种物品，每种物品都有给定的体积和价值。

在小泽看来，合理的背包安排方案是这样的：每个人背包里装的物品的总体积恰等于包的容量。每个包里的每种物品最多只有一件，但两个不同的包中可以存在相同的物品。

任意两个人，他们包里的物品清单不能完全相同。在满足以上要求的前提下，所有包里的所有物品的总价值最大是多少呢？

题解

P1858 多人背包

其实就是求 \texttt01 背包前 k 优解的价值和，我们只要求出前 k 优解，再求和即可。

求前 k 优解时，我们可以在 \texttt01 背包的基础上再加以为 p，表示第 p 优解，更新时先算出状态 dp_{j-v_i}+w_i 的前 k 优解，再让它和 dp_j 的前 k 优解归并排序，取前 k 个即可。

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;
long long read() {
    long long x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
void write(long long x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const int K = 60, V = 5010, N = 210;
int k, v, n, a, b, dp[V][K], r[K << 1], ans;
int main() {
    k = read();
    v = read();
    n = read();
    memset(dp, 0xcf, sizeof(dp));
    dp[0][1] = 0;
    for (int i = 1; i <= n; i++) {
        a = read();
        b = read();
        for (int j = v; j >= a; j--) {
            int x = 1, y = 1, t = 0;
            while (x <= k && y <= k) {
                if (dp[j][x] > dp[j - a][y] + b)
                    r[++t] = dp[j][x++];
                else
                    r[++t] = dp[j - a][y++] + b;
            }
            while (x <= k) r[++t] = dp[j][x++];
            while (y <= k) r[++t] = dp[j - a][y++] + b;
            for (x = 1; x <= k; x++) dp[j][x] = r[x];
        }
    }
    for (int i = 1; i <= k; i++) ans += dp[v][i];
    write(ans);
    return 0;
}

区间dp问题

\color{Green}100\color{Black}+\color{Green}100\color{Black}+\color{Green}100\color{Black}=\color{Green}300\color{Black}/\color{Gold}\text{Rank 1}

\color{#3498DB}\text{A. 字符串折叠}

题目

折叠的定义如下：

一个字符串可以看成它自身的折叠。记作 S=S。

如果 $A=A',B=B'$，则 $AB=A'B'$，例如，因为 $\texttt{3(A) = AAA, 2(B) = BB}$，所以 $\texttt{3(A)C2(B) = AAACBB}$，而 $\texttt{2(3(A)C)2(B) = AAACAAACBB}$。给一个字符串，求它的最短折叠。例如 $\texttt{AAAAAAAAAABABABCCD}$ 的最短折叠为：$\texttt{9(A)3(AB)CCD}$。 ### 题解 [P4302 [SCOI2003]字符串折叠](https://www.luogu.com.cn/problem/P4302) 设 $dp_{i,j}$ 表示把区间 $[i,j]$ 折叠的最小长度，若不折叠，那么我们可以把 $[i,j]$ 分成两个区间计算答案，即 $dp_{i,j}\leftarrow dp_{i,k}+dp_{k+1,j}$。若选择折叠，则我们只需折叠一个完整的周期串即可，我们先假设 $[i,j]$ 是个周期串，枚举它的周期 $[i,k]$，比较是否是周期串并计算答案即可。答案为 $dp_{1,n}$。 ### 代码 ```cpp #include <bits/stdc++.h> #define ll long long using namespace std; long long read() { long long x = 0, f = 1; char ch = getchar(); while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)) { x = x * 10 + ch - 48; ch = getchar(); } return x * f; } void write(long long x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); } const int N = 110; string s, str[N][N], p; int n, dp[N][N]; string turn(int x) { if (!x) return ""; return turn(x / 10) + char(x % 10 + '0'); } int main() { cin >> s; n = s.size(); s = " " + s; memset(dp, 0x3f, sizeof(dp)); for (int i = 1; i <= n; i++) { dp[i][i] = 1; str[i][i] = s[i]; for (int j = i + 1; j <= n; j++) str[i][j] = ""; } for (int len = 2; len <= n; len++) { for (int l = 1; l + len - 1 <= n; l++) { int r = l + len - 1; for (int i = l; i < r; i++) { if (dp[l][r] > dp[l][i] + dp[i + 1][r]) { dp[l][r] = dp[l][i] + dp[i + 1][r]; str[l][r] = str[l][i] + str[i + 1][r]; } } for (int i = 1; i < len; i++) { if (len % i) continue; bool flag = 0; for (int j = i; j + l <= r; j++) if (s[j + l] != s[j % i + l]) { flag = 1; break; } if (flag) continue; p = turn(len / i); if (dp[l][r] > dp[l][l + i - 1] + 2 + p.size()) { dp[l][r] = dp[l][l + i - 1] + 2 + p.size(); str[l][r] = p + "(" + str[l][l + i - 1] + ")"; } } } } cout << dp[1][n] << endl; return 0; } ``` ## $\color{#3498DB}\text{B. 关灯顺序}

题目

某一村庄在一条路线上安装了 n 盏路灯，每盏灯的功率有大有小（即同一段时间内消耗的电量有多有少）。老张就住在这条路中间某一路灯旁，他有一项工作就是每天早上天亮时一盏一盏地关掉这些路灯。

为了给村里节省电费，老张记录下了每盏路灯的位置和功率，他每次关灯时也都是尽快地去关，但是老张不知道怎样去关灯才能够最节省电。他每天都是在天亮时首先关掉自己所处位置的路灯，然后可以向左也可以向右去关灯。开始他以为先算一下左边路灯的总功率再算一下右边路灯的总功率，然后选择先关掉功率大的一边，再回过头来关掉另一边的路灯，而事实并非如此，因为在关的过程中适当地调头有可能会更省一些。

现在已知老张走的速度为 1m/s，每个路灯的位置（是一个整数，即距路线起点的距离，（单位：m、功率（W）），老张关灯所用的时间很短而可以忽略不计。

请你为老张编一程序来安排关灯的顺序，使从老张开始关灯时刻算起所有灯消耗电最少（灯关掉后便不再消耗电了）。

题解

P1220 关路灯

设 dp_{l,r,0} 表示关掉 [l,r] 的所有灯并走到了 l 位置的最少耗电量，dp_{l,r,1} 表示关掉 [l,r] 的所有灯并走到了 r 位置的最少耗电量，sum_i 表示功率的前缀和 \sum_{j=1}^iP_j，a_i 为第 i 个路灯的位置。

考虑只在某一个状态的基础上向左或向右走一步，注意是可以调头的：

dp_{l,r,0}\leftarrow dp_{l+1,r,0}+(sum_l+sum_n-sum_r)\times (a_{l+1}-a_l)

dp_{l,r,0}\leftarrow dp_{l+1,r,1}+(sum_l+sum_n-sum_r)\times (a_{r}-a_l)

dp_{l,r,1}\leftarrow dp_{l,r-1,1}+(sum_{l-1}+sum_n-sum_{r-1})\times (a_{r}-a_{r-1})

dp_{l,r,1}\leftarrow dp_{l,r-1,0}+(sum_{l-1}+sum_n-sum_{r-1})\times (a_{r}-a_l)

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;
long long read() {
    long long x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
void write(long long x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const int N = 1010, M = 1e4 + 10;
int n, c, a[N];
ll p[N], dp[N][N][2], sp[M], sip[M];
ll tl(int l, int r) { return r * (sp[r] - sp[l - 1]) - (sip[r] - sip[l - 1]); }
ll tr(int l, int r) { return sip[r] - sip[l - 1] - l * (sp[r] - sp[l - 1]); }
ll other(int l, int r) { return sp[10000] - sp[a[r]] + sp[a[l]]; }
int main() {
    n = read();
    c = read();
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        p[i] = read();
        sp[a[i]] += p[i];
        sip[a[i]] += a[i] * p[i];
    }
    for (int i = 1; i <= 10000; i++) {
        sp[i] += sp[i - 1];
        sip[i] += sip[i - 1];
    }
    memset(dp, 0x3f, sizeof(dp));
    dp[c][c][0] = dp[c][c][1] = 0;
    for (int l = c; l >= 1; l--) {
        for (int r = c; r <= n; r++) {
            if (l == r)
                continue;
            dp[l][r][0] = min(dp[l + 1][r][0] + other(l, r) * (a[l + 1] - a[l]),
                              dp[l + 1][r][1] + other(l, r) * (a[r] - a[l]));
            dp[l][r][1] = min(dp[l][r - 1][1] + other(l - 1, r - 1) * (a[r] - a[r - 1]),
                              dp[l][r - 1][0] + other(l - 1, r - 1) * (a[r] - a[l]));
        }
    }
    write(min(dp[1][n][0], dp[1][n][1]));
    return 0;
}

\color{#9D3DCF}\text{C. 字符合并}

题目

有一个长度为 n 的 \texttt{01} 串，你可以每次将相邻的 k 个字符合并，得到一个新的字符并获得一定分数。

得到的新字符和分数由这 k 个字符确定。你需要求出你能获得的最大分数。

题解

P3736 [HAOI2016]字符合并

字符不同，合成的价值和结果就不同，因此我们可以在传统区间 \text{DP} 的基础上添加一维 s 表示区间 \texttt{01} 串合并后的状态。

设 dp_{i,j,s} 表示区间 [l,r] 合并后状态为 s 的最大收益，由于只要是长度不小于 k 的 \texttt{01} 串都可以合并，且每次合并的价值是正数，因此一段长度为 len 的区间采用最优的方式合并后的字符数量一定小于 k 且是定值 x=(len-1)\bmod(k-1)+1。

若 x\neq1，则区间 [l,r] 不能最终合并为一个字符，我们可以把它分成左右两个区间，一个区间剩 x-1 个字符，一个剩 1 个字符，合并起来即可，根据前面提到的 len 确定 x 也确定，x 确定了 len 就只有 \frac{r-l}{k-1} 个左右。
若 x=1，则区间 [l,r] 最终会合并为 1 个字符，我们可以参照 x\neq 1 的情况求出 [l,r] 剩 k 个字符的最优方案，再按照题目给出的合并分数计算最大值即可。

时间复杂度为 O(\frac{n^3}{k}2^{k-1})。

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;
long long read() {
    long long x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
void write(long long x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const int N = 310, S = 256;
int n, k, c[N];
ll e[N], w[N], dp[N][N][S], ans = -1e9;
int main() {
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    n = read();
    k = read();
    memset(dp, 0xcf, sizeof(dp));
    for (int i = 1; i <= n; i++) {
        c[i] = read();
        dp[i][i][c[i]] = 0;
    }
    for (int i = 0; i < (1 << k); i++) {
        e[i] = read();
        w[i] = read();
    }
    for (int len = 2; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1, x = (len - 1) % (k - 1);
            if (!x)
                x = k - 1;
            for (int mid = r - 1; mid >= l; mid -= (k - 1)) {
                for (int s = 0; s < (1 << x); s++) {
                    dp[l][r][s << 1] = max(dp[l][r][s << 1], dp[l][mid][s] + dp[mid + 1][r][0]);
                    dp[l][r][s << 1 | 1] = max(dp[l][r][s << 1 | 1], dp[l][mid][s] + dp[mid + 1][r][1]);
                }
            }
            if (x == k - 1) {
                ll f[2] = { dp[0][0][0], dp[0][0][0] };
                for (int s = 0; s < (1 << k); s++) f[e[s]] = max(f[e[s]], dp[l][r][s] + w[s]);
                dp[l][r][0] = f[0];
                dp[l][r][1] = f[1];
            }
        }
    }
    for (int i = 0; i < (1 << k); i++) ans = max(ans, dp[1][n][i]);
    write(ans);
    return 0;
}