这就是我们上面问题的模板。代码中顺便展示记忆化搜索+剪枝的解法：

/*
1.差值dp
设dp[i][j]表示选了前i个物品，两堆积木差值为j时第一堆积木的高度（这个状态是精髓！）
那么显然有以下三种转移：
不选i，      dp[i][j]<-dp[i-1][j]
选i放第一堆，dp[i][j]<-dp[i-1][j-a[i]]+a[i]
选i放第二堆，dp[i][j]<-dp[i-1][j+a[i]]      // 注意这里不要加上a[i]，因为状态存的是第一堆积木的高度还有一个问题，因为存储的是差值，所以第二维可能有负数。
考虑将第二维向上平移500000个，这样0~499999的是负数，500001~1000000的是正数，500000表示0又发现第i行的状态转移只和第i-1行有关，可以滚动数组优化空间------------------------------------------------------------2.爆搜优化：剪枝+记忆化
不加优化爆搜就是01选择类的dfs，判断每个物品是选给第一堆还是第二堆，时间复杂度O(2^n)
考虑先剪枝一下:
1.可行性剪枝。如果当前第一堆加上剩余所有都达不到第二堆高度，显然无解。第二堆同理
2.最优性剪枝。记录当前的最大答案ans，如果第一堆加上剩余所有方块都无法达到ans，显然这个状态不优。如果两堆和剩下所有加起来无法达到2*ans，显然也不优。第二堆同理
3.搜索顺序剪枝。发现答案具有不依赖顺序的特点（按照不同的顺序叠都行，只要最后高度不一样就行）所以考虑对所有积木降序排序。这样DFS时会优先选择较大的数。较大的数更容易接近目标值，从而更快地触发剪枝条件，减少无效搜索。
然后发现dfs会重复搜到许多一样的状态，所以考虑用一个记忆化数组存储当前状态的答案，这样就可以极大优化时间复杂度
由于这道题值域过大，考虑用map来实现记忆化------------------------------------------------------------发现不行的情况即为最大高度为0的情况，输出-1
*/#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxh = 1e6 + 7, zero = 5e5;int n, a[60];// dp解法
void dp(){vector <int> f(maxh,-1e9); // f表示前一行(i-1)，g表示当前行(i)vector <int> g(maxh,-1e9); // 初始化为极小值，避免出错f[zero] = 0; // 给一个初状态f[0]for(int i = 1; i <= n; i ++){for(int j = 0; j <= 1e6; j ++){ // 只要遍历到所有元素的和即可g[j] = max(g[j], f[j]);                   // f[i][j]=max(f[i][j],f[i-1][j])if(j >= a[i]){g[j] = max(g[j], f[j - a[i]] + a[i]); // f[i][j]=max(f[i][j],f[i-1][j-a[i]]+a[i])}if(j + a[i] <= 1e6){g[j] = max(g[j], f[j + a[i]]);        // f[i][j]=max(f[i][j],f[i-1][j+a[i]])}}f = g; // 把值滚动给下一行fill(g.begin(),g.end(),-1e9); // 重置g数组的值}cout << (f[zero] == 0? -1 : f[zero]) << '\n'; // 此时因为g的值已经没了，所以要输出f
}// -------------------------------------------------------------------// 搜索解法
int ans = -1e9;
int s[60]; // s是前缀和数组
map< tuple<int,int,int> , int > vis; // 考虑用map存状态int dfs(int now, int h1, int h2){// 终止条件if(now == n + 1){if(h1 == h2){ ans = max(ans, h1); return h1; }else return -1;}// 记忆化tuple <int,int,int> t = {now, h1, h2};if(vis.count(t)){return vis[t];}// 剪枝if(h1+h2 + s[n]-s[now-1] <= 2*ans)	return -1;if(h1 + s[n]-s[now-1] <= ans)		return -1;if(h2 + s[n]-s[now-1] <= ans)		return -1;if(h1 + s[n]-s[now-1] < h2)			return -1;if(h2 + s[n]-s[now-1] < h1)			return -1;// 返回即为三种情况取maxreturn vis[t] = max({ 0/*避免都是-1，和0取一下max*/,dfs(now+1,h1+a[now],h2), dfs(now+1,h1,h2+a[now]), dfs(now+1,h1,h2) });
}void search(){sort(a + 1, a + n + 1, greater<>()); // 降序排序，可以加快搜索（这样不合法的更容易被剪枝）for(int i = 1; i <= n; i ++){s[i] = s[i - 1] + a[i];}int sum = dfs(1, 0, 0);cout << (sum == 0? -1 : sum) << '\n';
}// -------------------------------------------------------------------signed main()
{ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);cin >> n;for(int i = 1; i <= n; i ++){cin >> a[i];}
//	dp();search();return 0;
}

这类题目还有另一种设状态的方法：设 $f[i][j]$ 表示前 $i$ 个数，两人分到的数差值为 $j$ 时两人一共能得到的最大钱数。

转移：

1. 不用第 $i$ 个数：$f[i][j]=f[i-1][j]$；
2. 把第 $i$ 个数给先手：$f[i][j]=f[i-1][j-a[i]]+a[i]$；
3. 把第 $i$ 个数给后手：$f[i][j]=f[i-1][j+a[i]]+a[i]$。（这里的转移有改动）

注：这道题用之前介绍的状态设计方法也可以。这里是为了演示。

得到答案之后，考虑“赌场”的操作。
两人平均分到 $x=\lfloor f[n][0]/2\rfloor$ 的钱，剩下 $\sum a[i]-x$ 的钱去赌场，双倍返现，所以两人都分得 $\sum a[i]-x$ 这些钱。

不用担心除不尽，因为题目要求两人拿到的钱数相同，所以 $f[n][0]$ 一定是一个偶数。

注意这道题还要用滚动数组优化。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1005, maxc = 1e5 + 7;int n, a[maxn], f[2][2 * maxc]; // 开二倍，避免越界
int sum = 0;void solve()
{cin >> n;for(int i = 1; i <= n; i ++){cin >> a[i]; sum += a[i];}memset(f, -0x3f, sizeof f); // 初始化为极小值f[0][0] = 0;for(int i = 1; i <= n; i ++){for(int j = 0; j <= sum; j ++){int x = !(i & 1), y = i & 1;f[y][j] = max({f[x][j], f[x][j + a[i]] + a[i], f[x][abs(j - a[i])] + a[i]});}}cout << sum - f[n & 1][0] / 2 << '\n';
}signed main()
{ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);solve();return 0;
}

这道题一看就是差值 dp，不过由线性 dp 被改到了网格上。

先考虑差值 dp 的经典状态：设 $f[i][j][d]$ 表示走到 $(i,j)$，当前两人取的数差值为 $d$ 时的方案数。

注意到这道题还有一个“最后一步必须由 uim 吸收”的限制，所以考虑再加一维表示取的人：

$f[i][j][d][0/1]$ 表示走到 $(i,j)$，当前两人取数差值为 $d$，最后一次是 小a/uim 取的方案数。

则转移显然：

1. uim 取：$f[i][j][d][1]+=f[i-1][j][d-a[i][j]][0]$，$f[i][j][d][1]+=f[i][j-1][d-a[i][j]][0]$；
2. 小 a 取：$f[i][j][d][0]+=f[i-1][j][d+a[i][j]][1]$，$f[i][j][d][0]+=f[i][j-1][d+a[i][j]][1]$。

初状态：$f[i][j][a[i][j]][0]=1$。
答案：$\sum f[i][j][0][1]$。

注意还要取模。不光整体答案要对 $10^9+7$ 取模，因为魔瓶只有 $k$ 的容量，所以差值的那一维也要对 $k+1$ 取模（不是 $k$！！！）。

补充：为什么取模的一般都是计数题，因为取模会让一个很大的数突然变得很小，从而无法统计答案。
例如对 $10^9$ 取模，会导致 $10^9$ 是一个特别小的 $0$，而 $10^9-1$ 却很大，大小关系就乱了。

这道题还有一些卡空间，不能全都开 long long，只在统计答案时开 long long。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;int n, m, k;
int a[801][801];
int f[801][801][20][2];void solve()
{cin >> n >> m >> k;k = k + 1; // 直接赋值为 k+1，好看一点for(int i = 1; i <= n; i ++){for(int j = 1; j <= m; j ++){cin >> a[i][j];f[i][j][a[i][j] % k][0] = 1; // 初始化}}for(int i = 1; i <= n; i ++){for(int j = 1; j <= m; j ++){for(int d = 0; d <= k; d ++){f[i][j][d][0] = (f[i][j][d][0] + f[i - 1][j][(d - a[i][j] + k) % k][1]) % mod;f[i][j][d][0] = (f[i][j][d][0] + f[i][j - 1][(d - a[i][j] + k) % k][1]) % mod;f[i][j][d][1] = (f[i][j][d][1] + f[i - 1][j][(d + a[i][j]) % k][0]) % mod;f[i][j][d][1] = (f[i][j][d][1] + f[i][j - 1][(d + a[i][j]) % k][0]) % mod;}}}ll ans = 0;for(int i = 1; i <= n; i ++){for(int j = 1; j <= m; j ++){(ans += f[i][j][0][1]) %= mod;}}cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);solve();return 0;
}