学到的新东西<map>离散化以及关于状态的思考；这里有一个初状态以及末状态；

在背包问题中，当我们使用map（或unordered_map）来存储动态规划的状态时，我们实际上是在实现一种离散化的过程。离散化是一种数据预处理技术，用于将大范围的数值映射到较小的、连续的范围内，以便更有效地存储和计算。

在背包问题中，背包的容量通常是一个较大的整数范围，但如果不是所有的容量都会被实际使用到（即，不是所有的物品组合都会导致每个可能的容量被访问），那么使用数组来存储DP状态将会非常浪费空间。而map（或unordered_map）则提供了一种按需分配空间的方式。

具体来说，当我们尝试更新一个背包容量为j的状态时，我们首先检查dp[j]是否已经被创建。如果j还没有被访问过，那么dp[j]在map中就不存在，此时我们可以安全地创建一个新的键值对来存储这个状态。如果j已经被访问过，那么dp[j]已经在map中存在，我们可以直接更新它的值。

这种方式的好处是，我们只为实际使用到的背包容量分配了空间，从而大大减少了内存的使用。同时，由于map内部使用了红黑树（对于map）或哈希表（对于unordered_map）来存储键值对，查找和更新操作的时间复杂度都是对数级别或接近常数级别的，因此效率也是可以接受的。

总结来说，使用map（或unordered_map）来实现背包问题的DP状态存储，不仅实现了离散化，减少了空间的使用，而且保持了较高的时间效率。

在动态规划问题中，我们通常要定义状态来表示某个阶段或某个子问题的解。在这个特定的问题中，状态 dp[i][j] 表示考虑前 i 个物品时，天平两端的质量差为 j 的情况下，较重一端能够达到的最大质量。

当我们考虑第 i 个物品时，我们有三种选择：

不放第 i 个物品：这种情况下，天平两端的质量差仍然为 j，我们继承前一个状态 dp[i-1][j] 的结果。
将第 i 个物品放在天平的左边：如果我们选择将第 i 个物品放在天平的左边，那么天平两端的质量差将会增加 a[i]（因为左边增加了质量）。因此，在只考虑前 i-1 个物品时，质量差应该为 j - a[i]，以便加上第 i 个物品后达到质量差 j。所以我们查看 dp[i-1][j-a[i]] 的值，并加上当前物品的质量 a[i]。
将第 i 个物品放在天平的右边：如果我们选择将第 i 个物品放在天平的右边，那么天平两端的质量差将会减少 a[i]（因为右边增加了质量，但我们是用“左减右”来定义质量差的，所以实际上是减少了）。因此，在只考虑前 i-1 个物品时，质量差应该为 j + a[i]，以便加上第 i 个物品后达到质量差 j。但这里需要注意的是，我们实际上只关心左边（较重的一端）的总质量，所以我们直接查看 dp[i-1][j+a[i]] 的值（它表示在质量差为 j+a[i] 时左边能达到的最大质量）。
所以，j-a[i] 和 j+a[i] 分别是我们在考虑第 i 个物品之前的两种可能的质量差，它们分别对应着将第 i 个物品放在天平左边和右边的情况。
//一道极其有意思的变相的问题
#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const int N = 105 * 100 + 5;
int dp[105][2 * N], a[105];
int main() {
  int n, m;
  cin >> n >> m;
  for(int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  memset(dp, -0x3f, sizeof(dp));
  dp[0][0] = 0;
  for(int i = 1; i <= n; i++) {
    for(int j = 0; j <= N-100; j++) {
      dp[i][j] = dp[i - 1][j];
      dp[i][j] = max(dp[i][j], dp[i - 1][abs(j - a[i])] + a[i]);
      dp[i][j] = max(dp[i][j], dp[i - 1][j + a[i]] + a[i]);
    }
  }
  int ans = -1;
  for(int i = 0; i <= m; i++) ans = max(ans, dp[n][i]); 
  cout << ans << "\n";
  return 0;
}
```考虑三个子状态的过程完全就是nice，nice