目录
前言
背包
货币问题
分析
代码
砝码称重
分析
代码
区间dp
石子合并
分析
代码
游戏
分析
代码
前言
今天依旧不讲数论，明天我会把数论剩下的组合数求法和容斥原理补上，今天带来的是背包和区间dp的超级简单题总共四道。
背包
先来讲一下什么是背包问题，背包问题又被称为有限制的选法问题，注意这里的选法是没有顺序要求的。按照这个思路，如果我们发现一道dp问题没有对顺序的要求，那么就可以思考一下问题是不是某种背包模型了。
但是没有顺序的要求并不是说我们可以随便选，随便选的话很容易就会出现某个元素选的个数超过要求的情况，为了避免这种错误呢，背包问题一般都用前i个物品的所有选法作为划分，每次只在原来的基础上增加一种物品的选法，这样就可以很好的控制每种物品选择的数量，巧妙的避开了乱选的情况。
而又因为每种物品可能不止一个，所以我们又需要一维来枚举这个物品选择的个数，那么状态表示就变为了dp[i][j]，一般情况下背包问题都是二维的，少数情况可以优化到一维——参考01背包和完全背包这两种。（不会背包模板的同学请先移步至背包九讲专题_哔哩哔哩_bilibili）
讲完了背包问题的大致思路以后我们就来写两道题练练手。
货币问题
分析
可以发现题目与选择的顺序无关，只与选择的方案有关，所以我们就可以尝试能否通过背包来求解，发现对于每种货币都没有选择限制，所以考虑完全背包。
那么问题就转化成了完全背包求方案数，直接套模板就好。（注意这里的方案数空集要初始化为1——求方案数的dp问题一般都需要初始化空集，大家记住就好）
代码
//完全背包
#include<iostream>
using namespace std;
typedef long long LL;
const int N = 10010;
int n, v;
LL dp[N];
int nums[N];
int main()
{scanf("%d%d", &n, &v);for(int i = 0; i < n; i++)scanf("%d", nums + i);dp[0] = 1;for(int i = 0; i < n; i++)for(int j = nums[i]; j <= v; j++)dp[j] += dp[j - nums[i]];printf("%lld", dp[v]);return 0;
}砝码称重
分析
发现每种砝码可以分为选或不选两种情况，而且本题与选择的顺序无关只与选择的方案有关所以考虑01背包。（也可以说是状态机dp）
每种砝码选择的话需要分为两种情况——放左边或放右边。
显然因为左右只是相对的，所以我们的所有方案也可以分为两种情况（分别是正数域和负数域），对于这道题我们只考虑正数域。
不过这里有一个小细节，就是当枚举的重量小于当前砝码的重量时可能会变成负数，相对的一种选法在负数域时遇到这种情况也有可能会变成正数。
也可以这样考虑——所有结果为正数的情况只会由两种情况变化而来，即：正数变成正数，负数变成正数。
因为我们要考虑所有的正数的情况所以这种方案也要记录，具体操作就是取abs。
代码
/*每个砝码都三种状态：放左边，右边和不放，显然不放不会改变方案的总数，所以不考虑总量不会超过1e5,所以打表
*/
#include<iostream>
using namespace std;
const int N = 110, M = 1e5 + 10;
int n;
bool dp[N][M];
int nums[N];
int main()
{scanf("%d", &n);for(int i = 1; i <= n; i++)scanf("%d", nums + i);dp[0][0] = true;for(int i = 1; i <= n; i++)for(int j = 0; j <= 1e5 - nums[i]; j++)if(dp[i - 1][j]) //只用上一层的可以{dp[i][j] = true; dp[i][abs(j - nums[i])] = true;dp[i][j + nums[i]] = true;}int l = 0;for(int i = 1; i < M; i++)l += dp[n][i];printf("%d", l);return 0;
}区间dp
区间dp呢，我也没有做多少题，不是很了解。我能发现的区间dp大概可以理解为状态是区间，状态的子状态依旧是区间，所以对于区间dp问题我们就可以通过求子区间来推导出原区间。
石子合并
分析
区间dp的一道模板题，状态表示是dp[l][r]，两维分别代表区间的左端点和右端点。
状态转移：
dp[l][r] = min(dp[l][k] + dp[k + 1][r]) + s[r] - s[l - 1]
利用分治的思想将区间划分为两段，这样就可以利用子问题的结果求值了（s为前缀和数组）恍惚间觉得这道题好像讲过（
这道题注意一下初始化即可，时间复杂度为O(n^3)
代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 310;
int n;
int nums[N];
int s[N];
int dp[N][N];
int main()
{scanf("%d", &n);for(int i = 1; i <= n; i++)scanf("%d", nums + i);memset(dp, 0x3f, sizeof dp);for(int i = 1; i <= n; i++){s[i] = s[i - 1] + nums[i];dp[i][i] = 0;}for(int i = 2; i <= n; i++) //枚举区间长度{for(int j = 1; j + i - 1 <= n; j++) //枚举左端点{int l = j, r = j + i - 1;for(int k = l; k < r; k++)dp[l][r] = min(dp[l][k] + dp[k + 1][r], dp[l][r]);dp[l][r] += s[r] - s[l - 1];}}printf("%d", dp[1][n]);return 0;
}游戏
分析
这游戏一点也不好玩QAQ。
说是区间dp但我认为这道题主要是思维 + 博弈论。
首先我们发现无论游戏如何进行A和B的总分都是不变的，而胜利的条件是一方大于另一方，可以写为A > B。
这里如果我们去枚举的话可以发现A和B是两种状态，这里有一个常见的小思路，就是移项将大小关系转化成差值：A - B > 0。（主播依稀记得前面有一道前缀和 + 贪心的题目也是使用这种思路优化。这就不得不提复盘的好处了，不然主播学一点忘一点。）这样优化以后就只需要考虑一个变量了。
之后就是我们博弈论的思考方式了，即——最差情况下的最好。
什么意思呢？其实就是双方都是绝顶聪明的，而01游戏的特点就是一方若是最好，那么另一方必然是最差，所以说这个最差是对方造成的，我们需要在这种情况下找出最优方案。
再加上我们前面的思路，我们选择求A - B的最大值，而对于A - B，可以划分为两个集合，一种是选择左端的最佳情况，可以表示为：
a[l] - (B - A)注意这里的A 和 B只是表示的相对状态并不是数值！
同理，另一端可以表示为a[r] - (B - A)，当前情况最优就是两者的最大值。
而求出了A - B = d如何求出A和B呢？
前面我们说了01游戏的特点是A + B = s，这是一个恒等式，所以接下来我们对两者联立，就可以求出：
A = (s + d) / 2
B = (s - d) / 2
接下来是代码。
代码
#include<iostream>
using namespace std;
const int N = 110;
int a[N];
int n, s;
int dp[N][N];
int dfs(int l, int r)
{if(l == r) return a[l];if(dp[l][r]) return dp[l][r];int x = a[l] - dfs(l + 1, r);x = max(a[r] - dfs(l, r - 1), x);return dp[l][r] = x;
}
int main()
{scanf("%d", &n);for(int i = 1; i <= n; i++){scanf("%d", a + i);s += a[i];}
int l = dfs(1, n); // 计算 A - Bprintf("%d %d", (s + l) / 2, (s - l) / 2); //01游戏return 0;
}
