牛客刷题-Day12
今日刷题：\(1056-1061\)
1057 [NOIP2001]统计单词个数
题目描述
给出一个长度不超过 \(200\) 的由小写英文字母组成的字母串（约定：该字串以每行 \(20\) 个字母的方式输入，且保证每行一定为 \(20\) 个）。要求将此字母串分成 \(k\) 份（\(1 < k ≤ 40\)），且每份中包含的单词个数加起来总数最大（每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串 this 中可包含 this 和 is，选用 this 之后就不能包含 th）。
单词在给出的一个不超过 \(6\) 个单词的字典中。
要求输出最大的个数。
输入描述
每组的第一行有 \(2\) 个正整数 \(p,k\)。
\(p\) 表示字串的行数，\(k\) 表示分为 \(k\) 个部分。
接下来的 \(p\) 行，每行均有 \(20\) 个字符。
再接下来有 \(1\) 个正整数 \(s\)，表示字典中单词个数。（\(1 ≤ s ≤ 6\)）
接下来的 \(s\) 行，每行均有 \(1\) 个单词。
输出描述
\(1\) 个整数，分别对应每组测试数据的相应结果。
示例
输入
1 3
thisisabookyouareaoh
4
is
a
ok
sab
输出
7
解题思路
参考：题解：P1026 [NOIP 2001 提高组] 统计单词个数
- 状态表示：\(f_{i,j}\) 表示将前 \(j\) 个字符划分为 \(i\) 份的所含单词数，求解最大值。
- 状态计算：枚举结尾，则 \(f_{i,j}=max\{f_{i,j},f_{i-1,t}+sum_{t+1,j}\}\)，这里 \(i-1 \le t\le j-1\)，\(sum_{i,j}\) 表示区间 \([i,j]\) 所含单词数的最大值。因为前面划分为 \(i\) 份至少含有 \(i\) 个字符串，而一个划分至少长度为 \(1\)，由此得到 \(t\) 的取值范围。
- \(sum_{i,j}\) 求解：因为选用一个单词，其所在首字母位置不能使用，因此如果 \(i\) 处开始无单词匹配，则 \(sum_{i,j}=sum_{i+1,j}\)；否则 \(sum_{i,j}=sum_{i+1,j}+1\)。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 210, M = 50;string str, s;
int p, k, n, m;
vector<string> dict;
int f[M][N]; // 分为 i 份且 j 为结尾所含单词数
int sum[N][N]; // [i, j] 包含单词数bool check(int a, int b) {int len = b - a + 1;int maxlen = 0;for (int i = 0; i < n; i++) maxlen = max(maxlen, (int) dict[i].size());if (len > maxlen)return false;for (int i = 0; i < n; i++) {if (len < dict[i].size())continue;if (str.substr(a, dict[i].size()) == dict[i])return true;}return false;
}void solve() {for (int l = m; l >= 1; l--) {if (check(l, l))sum[l][l] = 1;for (int r = l + 1; r <= m; r++) {sum[l][r] = sum[l + 1][r];for (int len = 2; l + len - 1 <= r; len++) {if (check(l, l + len - 1))sum[l][r] = max(sum[l][r], sum[l + 1][r] + 1);}}}for (int i = 1; i <= m; i++)f[1][i] = sum[1][i];for (int i = 2; i <= k; i++) // 划分数for (int j = i; j <= m; j++) // 结尾for (int t = i - 1; t < j; t++) // 枚举上一次划分的结尾f[i][j] = max(f[i][j], f[i - 1][t] + sum[t + 1][j]);cout << f[k][m];
}int main() {cin >> p >> k;str = "#";for (int i = 1; i <= p; i++) {cin >> s;str = str + s;}cin >> n;for (int i = 1; i <= n; i++) {cin >> s;dict.push_back(s);}m = str.size() - 1;solve();return 0;
}
1058 Min酱要旅行
题目描述
从前有个富帅叫做 \(Min\) 酱，他很喜欢出门旅行，每次出门旅行，他会准备很大一个包裹以及一大堆东西，然后尝试各种方案去塞满它。
然而每次出门前，\(Min\) 酱都会有个小小的烦恼。众所周知，富帅是很讨妹子喜欢的，所以 \(Min\) 酱也是有大把大把的妹子，每次出门都会有一只妹子随行。然而这些妹子总是会非常排斥 \(Min\) 酱准备的众多东西中的一件（也许是因为这件东西是其它妹子送给 \(Min\) 酱的），这件东西 \(Min\) 酱是万万不敢带上的，否则的话……嘿嘿嘿。另外，妹子们嫌 \(Min\) 酱的包裹太丑了，会自带一个包裹去换掉 \(Min\) 酱的包裹。
\(Min\) 酱是个控制欲很强的人，然而这样一来，\(Min\) 酱就不知道可以用多少种方案去填充包裹了，所以 \(Min\) 酱很郁闷。
于是 \(Min\) 酱找到了聪明的你，希望你能帮助他解决这些问题。
另外，\(Min\) 酱是个典型的懒人，他不希望每次带不同的妹子出去都麻烦你，所以他希望你能给出有 \(K_1,...,K_n\) 件物品，第 \(i\) 件不能带并且包裹大小为 \(1...M\) 的所有方案数。
输入描述
可能有多组数据。对于每一组数据：
第一行，两个整数 \(n,m\)，分别表示物品数量和妹子带的包裹的最大容积。
第二行，\(n\) 个正整数，分别表示物品 \(K_i\) 的体积。
输出描述
对于每一组数据，输出一个 \(n×m\) 的矩阵，第 \(i\) 行 \(j\) 列表示包裹容积为 \(j\)，不能带 \(i\) 号物品时，装满包裹的方案总数。
为了美观起见，我们只保留方案数的个位。
示例
输入
3 2
1 1 2
输出
11
11
21
备注
\(1≤n,m≤2300，K_i ≤1000\)。
解题思路
- 状态表示：\(f_{i,j}\) 表示不选 \(i\) 且体积为 \(j\) 的方案数。
- 状态计算：首先考虑正常的 \(01\) 背包问题，求解得到 \(dp_{i,j}\)，表示前 i 个物品中选择且体积为 j 的方案数。如果当前体积小于 \(K_i\)，则必然不会选择第 \(i\) 个物品，\(f_{i,j}=dp_{i,j}\)；否则 \(f_{i,j}\) 需要在 \(dp_{i,j}\) 的基础上减去选择 \(i\) 且体积为 \(j\) 的方案数，即减去不选 \(i\) 体积为 \(j-K_i\) 的 \(dp\) 方案数。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2310;int n, m;
int a[N], dp[N], f[N]; // f[i][j] 表示不选 i 且体积为 j 的方案数int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++)scanf("%d", &a[i]);// 纯 01 背包dp[0] = 1;for (int i = 1; i <= n; i++) {for (int j = m; j >= a[i]; j--)dp[j] = (dp[j] + dp[j - a[i]]) % 10;}for (int i = 1; i <= n; i++) {for (int j = 0; j <= m; j++) {if (j < a[i])f[j] = dp[j];elsef[j] = (dp[j] - f[j - a[i]] + 10) % 10;}for (int j = 1; j <= m; j++)printf("%d", f[j]);printf("\n");}return 0;
}
1060 [SCOI2009]粉刷匠
题目描述
\(windy\) 有 \(N\) 条木板需要被粉刷。 每条木板被分为 \(M\) 个格子。 每个格子要被刷成红色或蓝色。
\(windy\) 每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。 每个格子最多只能被粉刷一次。
如果 \(windy\) 只能粉刷 \(T\) 次，他最多能正确粉刷多少格子？
一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。
输入描述
输入文件 paint.in 第一行包含三个整数 \(N, M, T\)。
接下来有 \(N\) 行，每行一个长度为 \(M\) 的字符串，0 表示红色，1 表示蓝色。
输出描述
输出文件 paint.out 包含一个整数，最多能正确粉刷的格子数。
示例1
输入
3 6 3
111111
000000
001100
输出
16
备注
\(30\%\) 的数据，满足 \(1≤N,M≤10\)；\(0≤T≤100\)。
\(100\%\) 的数据，满足 \(1≤N,M≤50\)；\(0≤T≤2500\)。
解题思路
参考：P4158 [SCOI2009]粉刷匠(分组背包问题+前缀和优化)
- 状态表示：将每个木板当作一个背包组，粉刷次数为背包容量，粉刷正确的格子数为价值，\(f_{i,j}\) 表示前 \(i\) 个木板涂 \(j\) 次的价值，求解最大值。
- 状态计算：\(f_{i,j}=max\{f_{i,j},f_{i-1,j-k}+g_{i,m,k}\}\)，\(g_{i,j,k}\) 表示第 \(i\) 个木板的前 \(j\) 个格子涂 \(k\) 次的最大价值。那么需要先求解 \(g_{i,j,k}\)。\(g_{i,j,k}=max\{g_{i,j,k-1},g_{i,q,k-1}+max\{sum0,sum1\}\}\)，这里 \(sum\) 为第 \(i\) 个木板区间 \([q+1,j]\) 的红或者蓝格子数。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 55, M = 2510;int n, m, t; // n 看作背包组 t 看作背包容量 正确粉刷格子数为价值
char s[N][N];
int g[N][N][M]; // 第 i 条木板前 j 格子最多涂 k 次的价值
int f[N][M]; // 前 i 个木板涂 j 次的价值
int sum0[N][N], sum1[N][N];int main() {scanf("%d%d%d", &n, &m, &t);for (int i = 1; i <= n; i++) {scanf("%s", s[i] + 1);for (int j = 1; j <= m; j++) {if (s[i][j] == '1') {sum1[i][j] = sum1[i][j - 1] + 1;sum0[i][j] = sum0[i][j - 1];} else {sum0[i][j] = sum0[i][j - 1] + 1;sum1[i][j] = sum1[i][j - 1];}}}for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)for (int k = 1; k <= m; k++) {g[i][j][k] = g[i][j][k - 1];for (int q = 0; q < j; q++) {int a = sum0[i][j] - sum0[i][q];int b = sum1[i][j] - sum1[i][q];g[i][j][k] = max(g[i][j][k], g[i][q][k - 1] + max(a, b));}}for (int i = 1; i <= n; i++)for (int j = 1; j <= t; j++)for (int k = 0; k <= min(j, m); k++) // 木板涂的次数不会超过其长度f[i][j] = max(f[i][j], f[i - 1][j - k] + g[i][m][k]);printf("%d\n", f[n][t]);return 0;
}