多维dp题单

多维dp1:

题目链接: 2021-06-06 第三届太原理工大学程序设计竞赛新生赛(重现赛) F: 天元突破 红莲螺岩

题目大意: 给出一个人的初始位置和这个人的能量，当他能打过左右两个人中的一个的时候可以获得他的能量，问他能否从左端或者右端穿过，左右端有人， 不能输出-1，能的话输出最少需要用的时间

解题思路: 二维dp加上一个状态，三位dp[i][j][k]表示当前左边打到i右边打到j现在在左边0，右边1的最小花费当能打过左边的时候当前的最小值dp[i][j][0] = min(dp[i - 1][j][0] + a[i - 1].p - a[i].p, dp[i - 1][j][1] + b[i].p - a[i].p), sum[i][j]表示左边打到i右边打到j后得到的总的能量，所以当sum[i - 1][j] > a[i].v的时候就可以进行上面的转移，当在左边的时候与该情况类似

code: https://paste.ubuntu.com/p/5KWwTKhf97/

多维dp2:

题目链接: 2022-07-23 "蔚来杯"2022牛客暑期多校训练营2 K: Link with Bracket Sequence I

题目大意: 给出一个括号序列，再给出一个长度n求长度为n的且是当前括号序列母串的可能串有多少个

解题思路: f[i][j][k]分别表示母串走到第i个位置子串匹配到第j个位置(第j个位置前面万全匹配)并且左右括号差值为k的方案数，当j是0的时候显然前面的状态都能直接转移过来f[i][j][k] = (f[i - 1][j][k - 1] + f[i - 1][j][k + 1])，否则当j是一般情况的时候我们发现如果当前是左括号f[i][j][k] = (f[i - 1][j - 1][k - 1], f[i - 1][j][k + 1])，如果当前是右括号f[i][j][k] = (f[i - 1][j - 1][k + 1] + f[i - 1][j][k - 1])

code: https://paste.ubuntu.com/p/rgJzNWjSwk/

多维dp3:

题目链接: 2022-07-31 AtCoder Beginner Contest 262 D: AtCoder Beginner Contest 262

题目大意: 给出一串数据，求任选任意多个可以凑成的数据的平均数是整数的情况有多少个

解题思路: 一开始想的很简单f[i][j][k]表示前i个选j个模数是k但是仔细一想你也许会发现，转移的时候不选当前位置还好一点，但是发现选当前位置的转移方程是f[i - 1][j - 1][?]第三维该怎么写，可能有的人说(((k - a[i] % j + j) % j)但是这样的话相当于mod(j - 1)的模数是我们要转移来的位置，什么意思呢，就是(sum + x) % 3我们是从(sum) % 2转移过来的显然是不对的，应该从sum % 3转移过来才正确，但是这样转移对应的状态又不对了相当于前面选了j个，又是不对的，f[i][4][3]由f[i][3][1]转过来，sum是4，4+2=6%4不等于3，应该由f[i][4][1]转移过来才是对的，故取模的时候模数应该固定才对，要多加一维枚举模数

code: https://paste.ubuntu.com/p/rpgMzT5dbc/