动态规划基础

动态规划概论

楼梯

这给定一座有10级台阶的楼梯，我们要从下往上走，每跨一步只能向上走1级或者2级台阶，请问

一共有多少种走法呢？

方法1：搜索，我们写个dfs，依次枚举每一步向上走多少台阶，最后统计有多少可行的方案。如果要走100级台阶，搜索一年都不一定能搜索出来

方法2：组合数学我们先把走法的表示方式简化：用一个只包含1和2的序列表示从下到上每一步分别走了几级台阶;22222表示一共走了5步，每次走2级台阶，这是一种有效的走法;1111222表示一共走了7步，前四步走1级台阶，后三步走2级台阶，这也是有效的走法。接着枚举一共有几步走了2级台阶，就能算出有几步走了1级台阶，最后可以用组合数学算。10=10*1（10个1，共C(10,10)=1种)
=8*1+2（8个1,1个2，共C(9,8）=9种）
=6*1+2*2（6个1，2个2，共C(8，6)=28种）
=4*1+3*2（4个1，3个2，共C(7，4)=35种）
=2*1+4*2(2个1，4个2，共C(6，2)=15种）
=5*2（5个2，共C(5，5)=1种）共计1+9+28+35+15+1=89种。

方法3：递归考虑最后一步的情况，我们只能从第9级或者第8级走过去。不管走到第8级和第9级的过程，如果我们知道走到第8级的走法共有x种，走到第9级的走法有y种，那么走到第10级的走法呢？这一共有x+y种!我们把走到i级台阶的走法数量用f(i）来表示，有f(10)=f(8)+f(9)同理有f(9)=f(7)+f(8)，f(8)=f(6)+f(7)对于任意的n≥2，有f(n)=f(n-2)+f(n-1)。（其实就是个斐波那契）

方法4 动态规划
递归计算会出现很多的重复计算
用动态规划就可以解决这个问题，从头开始推，由小问题的最优推出大问题的最优

#include <bits/stdc++.h>
using namespace std;int n;long long f[51];
int main()
{cin>>n;f[0]=1;f[1]=1;for(int i=2;i<=n;i++){f[i]=f[i-1]+f[i-2];}cout<<f[n];return 0;
}

最短路

#include <bits/stdc++.h>
using namespace std;int a[1001][1001],f[1001],n,m;int main()
{cin>>n>>m;memset(a,127,sizeof a);for(int i=1;i<=m;i++){int x,y,z;cin>>x>>y>>z;a[x][y]=min(a[x][y],z);}	memset(f,127,sizeof(f));f[1]=0;for(int i=2;i<=n;i++){for(int j=1;j<i;j++){if(f[j]<1<<30&&a[j][i]<1<<30){f[i]=min(f[i],f[i]+a[j][i]);}}}cout<<f[n];return 0;
}

最长上升子序列（LIS)

#include <bits/stdc++.h>
using namespace std;int n,a[1001],f[1001];
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){f[i]=1;for(int j=1;j<i;j++){if(a[j]<a[i]){f[i]=max(f[i],f[j]+1);}}}int ans=0;for(int i=1;i<=n;i++){ans=max(ans,f[i]);}cout<<ans;return 0;
} 

最长公共子序列（LCS)

#include <bits/stdc++.h>
using namespace std;int n,m,a[1001],b[1001],f[1001][1001]; 
int main()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=m;i++){cin>>b[i];}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){f[i][j]=max(f[i-1][j],f[i][j-1]);if(a[i]==b[j]){f[i][j]=max(f[i][j],f[i-1][j-1]+1);}}}cout<<f[n][m];return 0;
} 

#include <bits/stdc++.h>
using namespace std;int n,m,a[1001],b[1001],f[1001][1001]; 
int main()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=m;i++){cin>>b[i];}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){f[i][j]=max(f[i-1][j],f[i][j-1]);if(a[i]==b[j]){f[i][j]=max(f[i][j],f[i-1][j-1]+1);}}}cout<<f[n][m];return 0;
} 

最长回文子串

传送门
给定一个字符串，请你求出其中的最长回文子串的长度。

例如，给定字符串 Is PAT&TAP symmetric?，最长回文子串为 s PAT&TAP s，其长度是 $11$。

输入格式

包含一个非空字符串。

输出格式

输出一个整数，表示给定字符串的最长回文子串的长度。

数据范围

给定字符串的长度不超过 $1000$。

输入样例：

Is PAT&TAP symmetric?

输出样例：

11

方法1
由于回文串是对称的，所以我们可以枚举所有的中点，再向两侧扩散，时间复杂度为O（n^2）。

//中点扩散算法
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int dp[N][N];
int main()
{string str;getline(cin,str);int res=0;for(int i=0;i<str.length();i++){int l=i-1,r=i+1;//判断奇数长度回文串while(l>=0&&r<str.length()&&str[l]==str[r]) l--,r++;res=max(res,r-l-1);l=i,r=i+1;//判断偶数长度回文串while(l>=0&&r<str.length()&&str[l]==str[r]) l--,r++;res=max(res,r-l-1);}cout<<res<<endl;return 0;
}

方法2 动态规划
用动态规划来做上面的那个例题，dp[N][N]来存状态，dp[ i] [ j ]=1,表示字符串从i到j为回文串。
（1）当str[ i ]==str[ j ]时，dp[i+1][j-1]=1,则dp[ i ][ j ]=1 ( [i+1,j-1]为回文串，且str[ i ]==str[ j ]则[i,j]为回文串 ),否则dp[ i ][ j ]=0。
（2）当str[ i ]!=str[ j ]时,dp[ i ][ j ]=0。           在遍历方面也要注意，如果按照i和j从小到大的顺序来枚举子串的两个端点,然后更新dp[i]lj],会无法保证dp[i + 1][ - 1]已经被计算过,从而无法得到正确的dp[i][i]。我们可以遍历长度，长度从小到达依次增加，每次判断出左右端点即可。           

//动态规划
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
bool dp[N][N];
int main()
{string str;getline(cin,str);//读入字符串int res=1;int n=str.length();for(int i=0;i<n;i++){dp[i][i]=true;if(i<n-1&&str[i]==str[i+1])//判断边界条件{res=2;dp[i][i+1]=true;}}for(int l=3;l<=n;l++)//遍历字符串长度，最小从3开始（最小为1，加上左右两边）{for(int i=0;i+l-1<n;i++)//左边界{int j=i+l-1;//右边界if(str[i]==str[j]&&dp[i+1][j-1]){dp[i][j]=1;res=l;//更新时，一定l>=res}}}cout<<res<<endl;return 0;
}

概率动态规划

用f[x]表示能走到x号城市的概率,那么f[1]=1

从x城走到y城概率f[y]+=f[x]/d[x]
其中d[x]表示从x号城市出发的高速公路有多少条

对于每个节点 i，将节点 i 的概率 f[i] 均分给它的每个邻接节点 c[i][j]，并且将这一部分概率累加到 f[c[i][j]] 中。
i = 2，c[2] = {3, 4, 5}，即从节点 2 出发，有边指向节点 3、4、5。
f[2] = 0.6，表示从节点 1 到节点 2 的概率为 0.6。
l = 3，即节点 2 有 3 个邻居（3、4、5）。

f[3] += f[2] / 3; // f[3] 增加 0.6 / 3 = 0.2
f[4] += f[2] / 3; // f[4] 增加 0.6 / 3 = 0.2
f[5] += f[2] / 3; // f[5] 增加 0.6 / 3 = 0.2

#include <bits/stdc++.h>
using namesapace std;int n,m;
vector<int> c[101];
double f[101];
int main()
{cin>>n>>m;for(int i=1;i<=m;i++){int x,y;cin>>x>>y;c[x].push_back(y);}memset(f,0,sizeof (f));f[1]=1;for(int i=1;i<n;i++){int l=c[i].size();for(int j=0;j<l;j++)//边界条件不使用c[i].size,因为这是o(n)的复杂度 {f[c[i][j]]+=f[i]/l;}}return 0;
}

区间动态规划

石子合并

递归

#include <bits/stdc++.h>
using namespace std;int n,a[501],s[501];int solve(int l,int r){if(l==r){return 0;}int ans=1<<30;for(int m=l;m<r;m++){ans=min(ans,solve(l,m)+solve(m+1,r));}return ans+s[r]-s[l-1];}
int main()
{cin>>n;for(int i=l;i<=n;i++){cin>>a[i];}for(int i=l;i<=n;i++){s[i]=s[i-1]+a[i];}cout<<solve(1,n);return 0;
} 

#include <bits/stdc++.h>
using namespace std;int n,a[501],s[501],f[501][501];int solve(int l,int r){if(f[l][r]!=-1){return f[l][r];} if(l==r){return f[l][r]=0;}int ans=1<<30;for(int m=l;m<r;m++){ans=min(ans,solve(l,m)+solve(m+1,r));}return ans+s[r]-s[l-1];}
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){s[i]=s[i-1]+a[i];}memset(f,255,sizeof f);cout<<solve(1,n);return 0;
} 

#include <bits/stdc++.h>
using namespace std;int n,a[501],s[501],f[501][501];int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){s[i]=s[i-1]+a[i];}memset(f,127,sizeof(f));for(int i=1;i<=n;i++){f[i][i]=0;}for(int i=1;i<n;i++){for(int j=1;j<=n-i;j++){for(int k=j;k<j+i;k++){f[j][j+i]=min(f[j][j+i],f[j][k]+f[k+1][j+i]+s[j+i]-s[j-1]);}}}cout<<f[1][n];return 0;
} 

括号序列

#include <bits/stdc++.h>  // 包含常用的头文件，如 iostream, vector, algorithm 等
using namespace std;int n, f[501][501];  // n: 括号序列的长度，f: 动态规划表，f[i][j] 表示从第 i 个括号到第 j 个括号的最大有效匹配括号对数
char str[511];  // 存储括号序列，大小为 511 是为了容纳括号序列及其编号从 1 开始（数组下标从 1 开始）int main()
{scanf("%d%s", &n, str + 1);  // 读取括号序列的长度 n 和括号序列字符串 str，从 str[1] 开始存储memset(f, 0, sizeof(f));  // 初始化 f 数组为 0，表示所有区间的最大匹配括号对数初始为 0// 遍历每个可能的子序列长度 ifor (int i = 1; i < n; i++) {  // i 表示当前子序列的长度，遍历从 1 到 n-1// 遍历子序列的起始位置 j，j 表示当前子序列的起始位置for (int j = 1; j <= n - i; j++) {  // j 表示起始位置，保证子序列长度为 i，不越界// 处理括号匹配的情况：首先检查是否是括号对 '()' 或 '[]' 的情况if ((str[j] == '(' && str[j + 1] == ')') || (str[j] == '[' && str[j + i] == ']')) {// 如果当前括号是匹配的括号对，则更新动态规划表f[j][j + i] = f[j + 1][j + i - 1] + 2;  // 当前匹配对加上内层匹配的得分}// 对于每个可能的分割点 k，尝试分割子串来更新最优解for (int k = j; k < j + i; k++) {  // k 是分割点，遍历 [j, j+i] 区间的所有可能分割// f[j][j+i] 表示从 j 到 j+i 的最大匹配括号对数f[j][j + i] = max(f[j][j + i], f[j][k] + f[k + 1][j + i]);// 计算通过分割子串 [j, k] 和 [k+1, j+i] 的最大得分}}}cout << f[1][n];  // 输出最终从 1 到 n 的最大有效括号对数return 0; 
}

石子合并（环形）

然后这也是一个非常经典的套路，就是我们这种圈的情况，我们就把它连成两倍，然后再连成两倍上面做，然后最后就是考虑f(1)(n)考虑f(2)(n+1)。就是圆圈的情况，很多情况下都是可以这样做，其实你就会把每一条边删掉，以后情况你都能够考虑进去。就f(1)(n)就是考虑的是1到n的那条边删掉情况f(2) (n+1)就是2到那个n+1的那条边删掉情况f(3)到(n+2)就是3到1的那条边被删掉情况，你就能把所有情况。情况都考虑完。那么，这个事情复杂度就变成了n3方大,就是你会发现你把它倍增以后，就你把它一模一样，后面屁股上又接上去了，以后你n3方做完以后你就把删除，每条边的情况你都已经考虑到。

这段代码是动态规划的核心部分，目的是计算合并石子堆时最小的得分。这里 i 表示子序列的长度，而 f 数组用来存储从堆 j 到堆 j + i 的最小合并得分。

代码分析：

for (int i = 1; i <= n; i++) {for (int j = 1; j <= n - i; j++) {for (int k = j; k < j + i; k++) {f[j][j + i] = min(f[j][j + i], f[j][k] + f[k + 1][j + i] + s[j + i] - s[j - 1]);}}
}

• 外层循环： for (int i = 1; i <= n; i++)

  • i 表示当前子问题的长度，即正在考虑的子序列的长度。
  • i 从 1 到 n，依次表示从长度为 1 的子序列到长度为 n 的子序列。

• 中层循环： for (int j = 1; j <= n - i; j++)

  • j 是当前子序列的起始位置，表示从位置 j 开始，长度为 i 的子序列。
  • 由于 j 和 i 决定了子序列的末尾位置 j + i，为了避免数组越界，j 最大值为 n - i。

• 内层循环： for (int k = j; k < j + i; k++)

  • k 用于在当前子序列 [j, j + i] 中选择一个分割点。
  • 子序列 a[j...j + i] 被划分为两部分：一部分是 a[j...k]，另一部分是 a[k+1...j + i]，并且 k 需要遍历整个子序列。

• 状态转移： f[j][j + i] = min(f[j][j + i], f[j][k] + f[k + 1][j + i] + s[j + i] - s[j - 1]);

  • 这是动态规划的状态转移公式。
  • f[j][j + i] 表示将子序列 a[j...j + i] 合并成一堆的最小得分。
  • 递推关系：选择一个分割点 k，计算两部分的最小得分 f[j][k] 和 f[k + 1][j + i]，加上合并这两部分的得分（即合并后的石子数），合并后的得分是 s[j + i] - s[j - 1]，即从位置 j 到 j + i 这一部分的总石子数。
  • 通过遍历所有可能的分割点 k，我们可以得到从 j 到 j + i 的最小得分。

具体举例：

假设我们有 4 堆石子，堆的石子数分别为 [a1, a2, a3, a4]，我们希望通过合并这些堆来最小化合并得分。

1. 第一轮（i = 1）:

   • 只考虑长度为 1 的子序列（即单个堆），f[j][j + 1] 表示单堆石子合并的代价为 0，因为每次合并需要至少两堆，所以 f[j][j + 1] = 0。

2. 第二轮（i = 2）：

   • 考虑长度为 2 的子序列 [j, j + 1]，即选择两个相邻的堆进行合并。
   • 对于每个子序列 [j, j + 2]，通过内层循环选择一个合并点 k，比如可以选择 k = j 或 k = j + 1，计算出最小合并得分。

3. 第三轮（i = 3）：

   • 考虑长度为 3 的子序列。我们会继续选择合适的分割点，计算最小得分。

4. 以此类推，直到 i = n，表示合并整个序列。

#include <bits/stdc++.h>  
using namespace std;int n, a[501], f[501][501], s[501];  // n: 石子堆的数量，a: 每堆石子的数量，f: 动态规划表，s: 前缀和数组int main()
{cin >> n;  // 读取石子堆的数量for (int i = 1; i <= n; i++)  // 输入每堆石子的数量{cin >> a[i];  // 读取第 i 堆的石子数量a[n + i] = a[i];  // 为了模拟环形数组，重复一遍前 n 堆石子}n *= 2;  // 扩展数组大小为 2n，处理环形问题// 计算前缀和数组 s[], s[i] 表示前 i 堆石子的总数for (int i = 1; i <= n; i++){s[i] = s[i - 1] + a[i];  // 前缀和，s[i] = s[i-1] + a[i]，表示前 i 堆石子的总数}memset(f, 127, sizeof(f));  // 初始化动态规划表 f，设置为较大的数，表示最小值未计算// 动态规划计算最小合并得分for (int i = 1; i <= n; i++)  // 遍历子序列的长度 i{for (int j = 1; j <= n - i; j++)  // 遍历子序列的起始位置 j{for (int k = j; k < j + i; k++)  // 遍历分割点 k{// 计算从 j 到 j+i 的子序列合并的最小得分f[j][j + i] = min(f[j][j + i], f[j][k] + f[k + 1][j + i] + s[j + i] - s[j - 1]);// f[j][j+i] 是从堆 j 到堆 j+i 的最小合并得分// f[j][k] 和 f[k+1][j+i] 是子问题的解，s[j+i] - s[j-1] 是当前合并的代价}}}int ans = 1 << 30;  for (int i = 1; i <= n / 2; i++)  // 查找从 1 到 n/2 的最小合并得分{ans = min(ans, f[i][i + n / 2 - 1]);  // 从 f[i][i + n/2 - 1] 中寻找最小得分cout << ans << endl;  // 输出最小的得分}return 0; 
}

树形动态规划

统计人数

dfs写法

#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct node{node *next;int where;
} *first[100001], a[100001];
int n, l, f[100001];
inline void makelist(int x,int y){//连一条从x到y的边a[++l].where = y;a[l].next = first[x];first[x] = &a[l];
}
inline void solve(int i){f[i] = 1;//一开始就自己一个人for (node *x = first[i]; x; x = x->next)//找所有的儿子{solve(x->where);f[i] += f[x->where];//加上儿子子树的个数}
}
int main()
{scanf("%d", &n);memset(first, 0, sizeof(first));l = 0;for (int i = 2; i <= n;i++){int x;scanf("%d", &x);makelist(x, i);}solve(1);//解决以1号点为子树的情况for (int i = 1; i <= n;i++)printf("%d ", f[i]);return 0;
}

bfs写法

#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct node
{node *next;int where;
} *first[100001], a[100001];
int n, l, f[100001], c[100001];
inline void makelist(int x, int y)
{ // 连一条从x到y的边a[++l].where = y;a[l].next = first[x];first[x] = &a[l];
}
int main()
{scanf("%d", &n);memset(first, 0, sizeof(first));l = 0;for (int i = 2; i <= n; i++){int x;scanf("%d", &x);makelist(x, i);}c[1] = 1;//队列，找出bfs序for (int k = 1, l = 1; l <= k; l++){int m = c[l];//头元素for (node *x = first[m]; x; x = x->next)//下属点c[++k] = x->where;}for (int i = n; i; i--)//倒着算的，算到前面的时候后面都计算过了{int m = c[i];f[m] = 1;for (node *x = first[m]; x; x = x->next){f[m] += f[x->where];}}for (int i = 1; i <= n; i++)printf("%d ", f[i]);
}

没有上司的舞会

#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct node
{node *next;int where;
} *first[100001], a[100001];
int n, l ,c[100001],v[100001];
ll f[100001][2];
inline void makelist(int x, int y)
{ // 连一条从x到y的边a[++l].where = y;a[l].next = first[x];first[x] = &a[l];
}
inline void solve(int i){f[i][1] = v[i];for (node *x = first[i]; x;x=x->next){solve(x->where);f[i][0] += max(f[x->where][0], f[x->where][1]);f[i][1] += f[x->where][0];}
}
int main()
{scanf("%d", &n);memset(first, 0, sizeof(first));l = 0;for (int i = 2; i <= n;i++){int x;scanf("%d", &x);makelist(x, i);}for (int i = 1; i <= n;i++)scanf("%d", &v[i]);solve(1);printf("%lld\n", max(f[1][0], f[1][1]));
}

背包

01背包

01背包问题

#include <bits/stdc++.h>
using namespace std;const int N=1e3+10;
int v[N],w[N];
int f[N][N];
int main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>v[i]>>w[i];}for(int i=1;i<=n;i++){for(int j=1;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];return 0;
}

看一下 f[i][j] 的计算公式：$f[i][j]=max(A,B)$。

只用到了 $$f[i-1][j]f[i-1][j-v_i]$$ ，即只用到了$f[i-1]$ 这一层，并且用到的体积为 $j$ 和 $j-v_i$，都是小于等于 j 的。

因此可以从体积为 V 开始，利用$f[i-1]$的数据，求解出 $f[i][j]$，把 $f[i][j]$放到 $f[i-1][j]$ 的位置上。这样 f 数组就能优化到一维了。并且，当 背包容量小于 $v_j$ 的时候，$f[i][j]$ = max{$f[i-1][j]$，0 } = $f[i-1][j]$。所以 j 只需要从 V 遍历到 $v_j$ 即可。

#include <bits/stdc++.h>
using namespace std;using ll=long long;const int N=1e3+10;
int v[N],w[N];
int f[N];
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>v[i]>>w[i];}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];return 0;
}

完全背包

完全背包
思路1
思路2

#include<iostream>
using namespace std;
const int N = 1010;
int f[N][N];
int v[N],w[N];
int main()
{int n,m;cin>>n>>m;for(int i = 1 ; i <= n ;i ++){cin>>v[i]>>w[i];}for(int i = 1 ; i<=n ;i++)for(int j = 0 ; j<=m ;j++){for(int k = 0 ; k*v[i]<=j ; k++)f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);}cout<<f[n][m]<<endl;return 0;
}

有了上面的关系，那么其实 k 循环可以不要了，核心代码优化成这样：

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int v[N],w[N];
int f[N][N];
int main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>v[i]>>w[i];}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]>=0)f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]); }}cout<<f[n][m];return 0;
}

f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);//01背包f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);//完全背包问题//0 1 背包代码优化这里有详细说明

#include<iostream>
using namespace std;
const int N = 1010;
int f[N];
int v[N],w[N];
int main()
{int n,m;cin>>n>>m;for(int i = 1 ; i <= n ;i ++){cin>>v[i]>>w[i];}for(int i = 1 ; i<=n ;i++)for(int j = v[i] ; j<=m ;j++){f[j] = max(f[j],f[j-v[i]]+w[i]);//注意了，这里的j是从小到大枚举，和01背包不一样}cout<<f[m]<<endl;
}

多重背包

多重背包
思路

#include <iostream>
#include <algorithm>using namespace std;
const int N = 110;int v[N], w[N], s[N];
int f[N][N];
int n, m;int main(){cin >> n >> m;for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i] >> s[i];for(int i = 1; i <= n; i ++){//枚举背包for(int j = 1; j <= m; j ++){//枚举体积for(int k = 0; k <= s[i]; k ++){if(j >=  k * v[i]){f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);}}}}cout << f[n][m] << endl;return 0;
}

分组背包

分组背包

#include <bits/stdc++.h>using namespace std;
const int N=110;
int n,m,k;
int s[N],v[N][N],w[N][N];
int f[N][N];
int main()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>s[i];for(int k=0;k<s[i];k++){cin>>v[i][k]>>w[i][k];}}for(int i=1;i<=n;i++){for(int j=0;j<=m;j++){f[i][j]=f[i-1][j];for(int k=0;k<s[i];k++){if(j>=v[i][k])f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);}}}cout<<f[n][m]<<endl;return 0;
}

因为只用到了第i-1列，所以可以仿照01背包的套路逆向枚举体积

#include<bits/stdc++.h>
using namespace std;const int N=110;
int f[N];
int v[N][N],w[N][N],s[N];
int n,m,k;int main(){cin>>n>>m;for(int i=0;i<n;i++){cin>>s[i];for(int j=0;j<s[i];j++){cin>>v[i][j]>>w[i][j];}}for(int i=0;i<n;i++){for(int j=m;j>=0;j--){for(int k=0;k<s[i];k++){    //for(int k=s[i];k>=1;k--)也可以if(j>=v[i][k])     f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);  }}}cout<<f[m]<<endl;
}