20230525第四次作业
A. Bone Collector
题目大意：骨头收藏家有一个容积为\(v\)的大袋子，有\(n\)种骨头，不同的骨头有不同的价值和体积。现在给出每个骨头的价值，计算出骨头收藏家可以得到的最大总价值。
数据范围：\(v\leq 1000, n \leq 1000\)
题解：这是一个典型的01背包问题，令f[i][j]表示选前\(i\)个物品，背包体积为\(j\)的最大价值，则我们有：
f[i][j] = f[i - 1][j], j < v[i]
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]), j >= v[i]
代码实现：
（1）递推代码：
时间复杂度：\(O(nv)\), 空间复杂度：\(O(nv)\).
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int t;
cin >> t;
while (t -- )
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> w[i];
for (int i = 1; i <= n; i ++ ) cin >> v[i];
memset(f, 0, sizeof f);
for (int i = 1; i <= n; i ++ )
for (int j = 0; j <= m; j ++ )
{
f[i][j] = f[i - 1][j];
if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
cout << f[n][m] << "\n";
}
return 0;
}
(2)记忆化搜索代码：
时空复杂度同(1)
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int dfs(int n, int m)
{
int &u = f[n][m];
if (~u) return u;
if (n == 0 || m < 0) return u = 0;
if (m < v[n]) return u = dfs(n - 1, m);
else return u = max(dfs(n - 1, m), dfs(n - 1, m - v[n]) + w[n]);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int t;
cin >> t;
while (t -- )
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> w[i];
for (int i = 1; i <= n; i ++ ) cin >> v[i];
memset(f, -1, sizeof f);
cout << dfs(n, m) << "\n";
}
return 0;
}
(3)滚动数组优化：
时间复杂度：\(O(nv)\), 空间复杂度：\(O(n)\).
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int t;
cin >> t;
while (t -- )
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> w[i];
for (int i = 1; i <= n; i ++ ) cin >> v[i];
memset(f, 0, sizeof f);
for (int i = 1; i <= n; i ++ )
for (int j = m; j >= v[i]; j -- )
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m] << "\n";
}
return 0;
}
B. ACboy needs your help
题目大意：ACboy这个学生在本学期有\(n\)门课程，并计划在最多\(m\)天内完成学习。他在每个课程上花费的时间将会影响他所获得的收益。如何安排这\(m\)天的学习时间，以最大化收益？
数据范围：\(1 \leq n \leq 100, 1 \leq m \leq 100\)
题解：这是一个典型的分组背包问题，在每一门课程上花费不同时间获得收益不同，但一门课程只能选一个时间，所以它们在一个组里，我们要确定\(n\)个组的情况下，每个组里最多选一个物品，背包体积为\(m\)下的最大收益。令f[i][j]表示考虑前\(i\)个组，且背包体积为\(j\)时的最大收益，则显然有f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i][1]] + w[1], f[i - 1][j - v[i][2]] + w[2], ..., f[i - 1][j - v[i][k]] + w[k])。
代码实现：
(1)递推代码：
时间复杂度：\(O(nm^2)\), 空间复杂度：\(O(n^2)\).
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int n, m;
int v[N][N], w[N][N];
int f[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
while (cin >> n >> m, n || m)
{
memset(f, 0, sizeof f);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
{
v[i][j] = j;
cin >> w[i][j];
}
for (int i = 1; i <= n; i ++ )
for (int j = m; j >= 1; j -- )
for (int k = 1; k <= m; k ++ )
{
if (j >= v[i][k])
f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
}
cout << f[m] << "\n";
}
return 0;
}
(2)记忆化搜索代码：
时空复杂度同(1)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int n, m;
int v[N][N], w[N][N];
int f[N][N];
int dfs(int x, int y)
{
int &u = f[x][y];
if (~u) return u;
if (x == 0 || y < 0) return u = 0;
for (int k = 0; k <= m; k ++ )
if (y >= v[x][k])
u = max(u, dfs(x - 1, y - v[x][k]) + w[x][k]);
return u;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
while (cin >> n >> m, n || m)
{
memset(f, -1, sizeof f);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
{
v[i][j] = j;
cin >> w[i][j];
}
cout << dfs(n, m) << "\n";
}
return 0;
}
C. 手机号码
题目大意：统计在给定的手机号区间[l, r]中，满足特定条件的手机号数量。满足条件的号码特征：至少有三个相邻的相同数字，且不包含数字8和4。手机号必须同时满足这两个特征才算符合条件。
数据范围：\(10^{10} \leq l \leq r \leq 10^{11}\)
题解：这是一个典型的数位dp问题，f[pos][u][v][st][_8][_4]表示在pos为的更高一位是u, 再高一位是v的，当前有无连续三个一样的数，8和4的情况分别是st,_8和_4的情况下，满足条件的手机号码的个数。通过递归的方式，从高位到低位遍历数字的每一位，累计满足条件的数字个数。在递归过程中，根据当前位的数字和跟高两位的数字，更新状态变量st、_8 和_4，并根据limit变量控制是否达到原本的数的上限。由此我们可以在get_num函数中利用dfs函数，统计从手机号10000000000到给定的手机号中满足条件的号码的个数，利用get_num(r) - get_num(l - 1)即可获得区间[l, r]中满足条件的手机号的个数。
代码实现：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
LL l, r;
int num[11];
LL f[11][11][11][2][2][2];
//f[pos][u][v][state][_8][_4]
// pos 当前位置
// u 上一位数字
// v 再上一位数字
// state 是否出现3个连续相同数字
// _8 是否出现8
// _4 是否出现4
LL dfs(int pos, int u, int v, bool st, bool _8, bool _4, bool limit)
{
if (_8 && _4) return 0;
if (!pos) return st;
LL &t = f[pos][u][v][st][_8][_4];
if (!limit && ~t) return t;
LL res = 0;
int up = limit ? num[pos] : 9;
for (int i = 0; i <= up; i ++ )
res += dfs(pos - 1, i, u, st || (i == u && i == v), _8 || (i == 8), _4 || (i == 4), limit && (i == up));
if (!limit) t = res;
return res;
}
LL get_nums(LL x)
{
int len = 0;
while (x)
{
num[++ len] = x % 10;
x /= 10;
}
if (len < 11) return 0;
memset(f, -1, sizeof f);
LL res = 0;
for (int i = 1; i <= num[len]; i ++ )
res += dfs(len - 1, i, 0, 0, i == 8, i == 4, i == num[len]);
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> l >> r;
cout << get_nums(r) - get_nums(l - 1) << "\n";
return 0;
}
D. 没有上司的舞会
题目大意：职员编号为\(1 - n\), 且职员间之间有从属关系，形成一棵以校长为根的树状结构。在宴会上，每邀请一个职员都会增加一定的快乐指数r[i]，但如果某个职员的直接上司也来参加宴会，那么该职员将不会参加。
数据范围：\(1 \leq n \leq 6000, -128 \leq r_i \leq 127, 1 \leq l, k \leq n\).
题解：这是一个典型的树形dp问题，我们可以发现每个节点有两种状态，分别是被选和没有被选，我们用f[i][1 or 0]表示状态，第二维是1表示\(i\)节点被选时的最大快乐值，为0表示\(i\)节点没有被选时的最大快乐值。根据题意，如果一个节点被选择，那么它的儿子节点都不能被选择，如果一个节点没有被选择，那么它的儿子节点可以被选择，也可以不被选择。所以我们有状态转移方程：\(f[i][1] = \sum f[son_i][0]\), \(f[i][0] = r[i] + \sum max(f[son_i][1], f[son_i][0])\)(\(son_i\)表示节点\(i\)的儿子节点的集合)，因此我们只需要找到这棵树的父节点，然后dfs即可。
代码实现：
时间复杂度：\(O(n)\), 空间复杂度：\(O(n)\).
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 6e3 + 10;
int n;
int r[N];
int e[N], ne[N], idx, h[N];
bool has_fa[N];
int f[N][2];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs(int rt)
{
f[rt][1] = r[rt];
for (int i = h[rt]; ~i; i = ne[i])
{
int j = e[i];
dfs(j);
f[rt][0] += max(f[j][0], f[j][1]);
f[rt][1] += f[j][0];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> n;
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i ++ ) cin >> r[i];
for (int i = 1; i < n; i ++ )
{
int l, k;
cin >> l >> k;
add(k, l);
has_fa[l] = true;
}
int rt;
for (int i = 1; i <= n; i ++ )
if (!has_fa[i])
{
rt = i;
dfs(rt);
}
cout << max(f[rt][0], f[rt][1]) << "\n";
return 0;
}