模型总结
分组背包的问题模板：有 n n n 件物品和一个大小为 m m m 的背包，第 i i i 个物品的价值为 w i w_i wi，体积为 v i v_i vi。同时，每个物品属于一个组，同组内最多只能选择一个物品。求背包能装载物品的最大总价值。
我们也可以说得高大上一点：有若干组物品，每组内的物品之间互斥。求最大背包价值。
分组背包的 dp 状态： d p [ i ] [ j ] dp[i][j] dp[i][j] 表示前 i i i 件物品，背包容量为 j j j 达到的最大价值
设 v [ i ] [ k ] v[i][k] v[i][k] 和 w [ i ] [ k ] w[i][k] w[i][k] 分别表示第i组第 k k k 个物品的体积、价值， s [ k ] s[k] s[k] 表示第 k k k 个组的元素数量，则转移如下：
d p [ i ] [ j ] = m a x { d p [ i − 1 ] [ j − v [ i ] [ k ] ] + w [ i ] [ k ] } dp[i][j]=max\{dp[i-1][j-v[i][k]]+w[i][k]\} dp[i][j]=max{dp[i−1][j−v[i][k]]+w[i][k]} 1 < = i < = n , v [ i ] [ k ] < = j < = m , 1 < = k < = s [ k ] 1<=i<=n,v[i][k]<=j<=m,1<=k<=s[k] 1<=i<=n,v[i][k]<=j<=m,1<=k<=s[k]
d p [ n ] [ m ] dp[n][m] dp[n][m] 即为答案（和 01 背包很像）
同理，也可以压成一维数组，注意压维后背包容量（ j j j）要倒着枚举，避免从已经更新的地方（同一行）转移。
不能从同一行转移的原因是：分组背包每一组只能选一个，如果从同一组转移的话就变成了“分组完全背包”（这个名是我胡诌的）
例1.小明爱上课
Description
小明非常喜欢上课，现在小明的课表有一些课，他可以通过课表选择上哪些课。
上课会有奖励，每门课上课时间长短不同奖励也会不一样，存在上课时间更长，奖励更少的情况。每一门课上课的总时长为整数。不同时长的奖励，题目数据中会给出。
对于每一门课，小明只可以上一次，现在小明一共有 m m m 分钟的时间可以安排上课，但是小明想要得到最大的奖励，聪明的你可以帮助小明解决这个问题吗？
Input Format
第一行，输入两个数 n n n 和 m m m ，表示课程的数目以及小明需要上课的时间。接下来包括 n n n 行，每行 m m m 个数，第 i i i 个数表示对于每门课上 i i i 分钟的奖励（ i i i 从 1 开始，每门课程只可以上一次）。
Output Format
输出一个数，表示最大的奖励值。
输入数据 1
2 3
3 2 1
3 2 1
输出数据 1
6
Hint
数据范围
对于 10% 的数据， 1 ≤ n ≤ 4 1 \leq n \leq 4 1≤n≤4 ， 1 ≤ m ≤ 4 1 \leq m \leq 4 1≤m≤4
对于 50% 的数据， 1 ≤ n ≤ 100 1 \leq n \leq 100 1≤n≤100 ， 1 ≤ m ≤ 100 1 \leq m \leq 100 1≤m≤100
对于 100% 的数据， 1 ≤ n ≤ 100 1 \leq n \leq 100 1≤n≤100 ， 1 ≤ m ≤ 100 1 \leq m \leq 100 1≤m≤100
1 ≤ 1 \leq 1≤ 奖励值 ≤ 1000 \leq 1000 ≤1000
样例说明
这里小明一共有三分钟，他第一门课上一分钟得到 3 个奖励值，第二门课上一分钟得到 3 个奖励值，最多得到了 6 个奖励值，这个时候还剩一分钟，他这一分钟可以选择不上课，因为这个时候也没有课可以上了，如果选择其他的方案的话这个最大奖励值会降低。
这是一道模板题，直接按照模板里的思路敲代码就行。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, a[105][105];
int dp[105][1005]; // dp[i][j]表示前i节课，还能上的时间为j分钟的最大奖励值
void solve()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++) cin >> a[i][j];
}
dp[0][0] = 0; // 初始化：前0节课，上了0分钟的奖励值是0（这一句不要也可以，但严谨起见可以加上）
for(int i = 1; i <= n; i ++){
for(int j = 0; j <= m; j ++){ // 注意这里枚举的是上课时间
dp[i][j] = dp[i - 1][j]; // 先赋值为上一次的值（不能放到下面的循环里，因为这样会导致多次赋值为这个值，会出错）
for(int k = 1; k <= m; k ++){ // 这里枚举的是a的下标
if(j >= k) dp[i][j] = max(dp[i - 1][j - k] + a[i][k], dp[i][j]);
}
}
}
cout << dp[n][m] << '\n';
}
signed main()
{
ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
solve();
return 0;
}
Code2（压维）
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, a[105][105];
int dp[1005]; // dp[j]表示当前还能上的时间为j分钟的最大奖励值
void solve()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++) cin >> a[i][j];
}
dp[0] = 0; // 初始化：前0节课，上了0分钟的奖励值是0（这一句不要也可以，但严谨起见可以加上）
for(int i = 1; i <= n; i ++){
for(int j = m; j >= 1; j --){ // 注意这里倒着枚举，避免从相同的行更新（因为分组背包一组只能选一个）
for(int k = 1; k <= m; k ++){
if(j >= k) dp[j] = max(dp[j - k] + a[i][k], dp[j]);
}
}
}
cout << dp[m] << '\n';
}
signed main()
{
ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
solve();
return 0;
}
例2.[ABC344D] String Bags
问题陈述
最初有一个空字符串 S S S。 此外，还有 1 , 2 , … , N 1, 2, \ldots, N 1,2,…,N 个包，每个包都包含一些字符串。 袋子 i i i 包含 A i A_i Ai 个字符串 S i , 1 , S i , 2 , … , S i , A i S_{i,1}, S_{i,2}, \ldots, S_{i,A_i} Si,1,Si,2,…,Si,Ai。
对于 i = 1 , 2 , … , N i = 1, 2, \ldots, N i=1,2,…,N，您将重复以下步骤：
选择并执行以下两个操作之一：
- 支付 1 日元，从 i i i 中选择一个字符串，并将其连接到 S S S 的末尾。
- 什么也不做。
给定字符串 T T T，求使最后的 S S S 等于 T T T 所需的最小金额。 如果无法使最后的 S S S 等于 T T T，则打印 -1。
限制因素
- T T T 是一个由小写英文字母组成的字符串，长度在 1 和 100 之间（含）。
- N N N 是介于 1 和 100 之间的整数，包含在内。
- A i A_i Ai 是介于 1 和 10 之间的整数，包括首尾两个整数。
- S i , j S_{i,j} Si,j 是由小写英文字母组成的字符串，长度在 1 和 10 之间（包括首尾数字）。
输入
输入内容由标准输入法提供，格式如下：
T
N
A_1
S_{1,1}
S_{1,2}
…
S_{1,A_1}
A_2
S_{2,1}
S_{2,2}
…
S_{2,A_2}
⋮
A_N
S_{N,1}
S_{N,2}
…
S_{N,A_N}
输出
将答案打印为整数。
题目描述
あなたは最初、空文字列 $ S $ を持っています。
さらに、文字列がいくつか入った袋 $ 1,2,\dots,N $ があります。
袋 $ i $ には $ A_i $ 個の文字列 $ S_{i,1},S_{i,2},\dots,S_{i,A_i} $ が入っています。
これから、以下の手順を $ i=1,2,\dots,N $ について繰り返します。
- 以下のふたつの行動のうち、どちらかを選択して行う。
- $ 1 $ 円を支払い、袋 $ i $ からちょうどひとつの文字列を選択して $ S $ の末尾に連結する。
- 何もしない。
文字列 $ T $ が与えられるとき、最終的に $ S $ と $ T $ を一致させるために必要な最小の金額を求めてください。
但し、どのようにしても最終的な $ S $ を $ T $ に一致させることができない場合、 -1 と出力してください。
输入格式
入力は以下の形式で標準入力から与えられる。
$ T $ $ N $ $ A_1 $ $ S_{1,1} $ $ S_{1,2} $ $ \dots $ $ S_{1,A_1} $ $ A_2 $ $ S_{2,1} $ $ S_{2,2} $ $ \dots $ $ S_{2,A_2} $ $ \vdots $ $ A_N $ $ S_{N,1} $ $ S_{N,2} $ $ \dots $ $ S_{N,A_N} $
输出格式
答えを整数として出力せよ。
样例 #1
样例输入 #1
abcde
3
3 ab abc abcd
4 f c cd bcde
2 e de
样例输出 #1
2
样例 #2
样例输入 #2
abcde
3
2 ab abc
3 f c bcde
1 e
样例输出 #2
-1
样例 #3
样例输入 #3
aaabbbbcccc
6
2 aa aaa
2 dd ddd
2 ab aabb
4 bbaa bbbc bbb bbcc
2 cc bcc
3 ccc cccc ccccc
样例输出 #3
4
提示
制約
- $ T $ は長さ $ 1 $ 以上 $ 100 $ 以下の英小文字からなる文字列
- $ N $ は $ 1 $ 以上 $ 100 $ 以下の整数
- $ A_i $ は $ 1 $ 以上 $ 10 $ 以下の整数
- $ S_{i,j} $ は長さ $ 1 $ 以上 $ 10 $ 以下の英小文字からなる文字列
Sample Explanation 1
例えば、以下のようにすると $ 2 $ 円で最終的な $ S $ と $ T $ を一致させることができ、これが必要な金額の最低値であることが示せます。 - $ i=1 $ について、袋 $ 1 $ から abc を選択し $ S $ の末尾に連結する。 $ S= $ abc となる。 - $ i=2 $ について、何もしない。 - $ i=3 $ について、袋 $ 3 $ から de を選択し $ S $ の末尾に連結する。 $ S= $ abcde となる。
Sample Explanation 2
どのようにしても最終的な $ S $ と $ T $ を一致させることができないので、 -1 と出力してください。😊
解题思路
这道题有点意思。是一道字符串背景下的背包问题。当然，也是分组背包。
这道题是针对字符串进行操作，我们可以进行题面转换，换成我们熟悉的样子。
把拼接的字符串转化为得到的价值，“还能拼接多长的字符串”转化为背包的剩余容量。
设dp[i][j]表示前i个组，“还能拼接的字符串长度”j的最小代价，则转移如下：
d p [ i ] [ j ] = m a x { d p [ i − 1 ] [ j − k . s i z e ( ) ] + 1 } dp[i][j] = max\{dp[i-1][j-k.size()]+1\} dp[i][j]=max{dp[i−1][j−k.size()]+1}
且仅当 “字符串k是目标字符串T中以位置j为结尾的子串” 时
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string T;
vector <string> s[105];
int n, a[105], dp[105][105];
// 字符串k是否为目标字符串T中以位置pos为结尾的子串
int check(int pos, string k){
// if(k.size() > pos+1) return 0; // 避免越界。因为string下标从0开始，所以是>=pos+1
// 这里可以举个例子：T="abcd" pos=2；如果k.size()<=3则可以，否则不行
for(int i = pos, j = k.size() - 1; i >= pos - (k.size() - 1) && j >= 0; i --, j --){ // i是T的指针、j是k的指针
// i的范围可以尝试一下：T="abcd" k="bc" pos=2，则应该从2遍历到1，即pos ~ pos-(k.size()-1)
if(T[i] != k[j]) return 0;
}
return 1;
}
void solve()
{
cin >> T >> n;
for(int i = 1; i <= n; i ++){
cin >> a[i];
for(int j = 0; j < a[i]; j ++){
string tmp; cin >> tmp; s[i].push_back(tmp);
}
}
// 初始化
memset(dp, 127, sizeof dp); // memset按照字节赋值，int有4字节，每个字节8比特。127二进制为(0111 1111)2，刚好可以把整个字节大体填满
for(int i = 0; i <= n; i ++) dp[i][0] = 0; // ！！！初始化：前i个，长度为0，要花的钱为0
// dp
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= T.size(); j ++){
dp[i][j] = dp[i - 1][j]; // 初始化一下，注意！不能发放在下面的循环中，这样每次循环都重新初始化一遍，会出错
for(string k : s[i]){
if(j < k.size() || check(j - 1, k) == 0) continue; // 不符合要求
dp[i][j] = min(dp[i][j], dp[i - 1][j - k.size()] + 1); // string下标从0开始，所以k.size()要-1
}
}
}
int ans = dp[n][T.size()];
cout << (ans == 2139062143? -1 : ans) << '\n'; // 输出答案
}
signed main()
{
ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
solve();
return 0;
}
End
这里是 YLCHUP，谢谢大家！
