开一个分享用于记录自己写过的DP题单
线性DP:
1. AcWing 313. 花店橱窗
Time: 2023.05.23
描述:n类花按顺序排成一排放在m个花盆里,给出每类花在不同花盆的美观度,求美观度和的最大值。
f[i,j]:= 第i类花只考虑放在前j个花瓶时的美观度最大值;
状态计算: f[i,j] = max{v[i,k] + f[i-1}[k-1]},
要留出i-1个花瓶放前面的花,计算好k的范围,i<=k<=j;
2. AcWing 318. 划分大理石
Time: 2023.05.25
描述:6种大理石价值为1-6,给出每种大理石数量,问能否分成两堆使价值相等。
乍一看是多重背包的计数dp,用f[i][j]表示只考虑选前i类大理石作为其中一堆的所有方案中,
价值刚好为j的方案数。但是方案数过大,会爆答案,只要有一种就可以了,用bool来存储;
不过物品个数和价值都很大,TLE了。用二进制拆分来优化,变成01背包。
bool f[i][j] := 只考虑选前i类大理石作为其中一堆的所有方案中,是否存在价值刚好为j的方案;
状态计算:f[i][j] = f[i-1][j] | f[i-1][j-vi];
f[1-6][0] = true;
3. AcWing 317. 陨石的秘密
Time:2023.05.26
描述:给你i对{},j对[],k对(),深度d,构造一字符串,满足[]里不能有(),{}里不能有[]和()
求字符串深度为d的方案数。
f[i][j][k][d] := 由i对{},j对[],k对()构成,深度<=d的字符串的方案数;
ans = f[i][j][k][d] - f[i][j][k][d-1];
以左边第一个括号的类型划分集合;S = (A)B, [A]B, {A}B,3种情况的方案数累加起来。
以[A]B为例,此时A没有{},f[i][j][k][d] += ΣbΣc f[0][b][c][d-1]*f[i][j-b-1][k-c][d];