背包 DP

http://oi.nks.edu.cn/zh/Contest/Details/2519

背包和其他 DP 的不同在于，背包将物体的“代价”加入了状态，以此更好地转移

背包中最典型的的模型是 $01$ 背包和完全背包，更难的需要用玄学做法和数据结构进行优化

单调队列优化多重背包

将背包以 $\bmod \ v $ 的余数进行分组，每一组中以单调队列维护最大值

启发式搜索解决大容量 01 背包

使用估价函数，先将物品按性价比排序，在搜索到一个状态时算出剩余物品中在剩余容量内所能获得的最大价值，如果小于当前最优解，直接剪枝

如果写法优秀，完全可以 $0$ 毫秒通过

不选某种物品下的 01 背包方案数

设 $f_{i,j}$ 表示前 $i$ 个物品体积为 $j$，的方案数，$g_{i,j}$ 表示在所有物品中不选第 $i$ 个物品且体积为 $j$ 的方案数

计算 $g_{i,j}$ 时，考虑在 $f_{n,j}$ 中剔除第 $i$ 个物品产生的影响

可得 $j < a_i$ 时，$g_{i,j} = f_{n,j}$

把第 $i$ 个物品当做最后一个物品考虑，有 $f_{n,j} = g_{i,j - a_i} + g_{i,j}$

所以 $j \ge a_i$ 时，$g_{i,j} = f_{n,j} - g_{i,j - a_i}$

f[0][0] = 1;
for (int i = 1; i <= n; i++)
{
	for (int j = 0; j < a[i]; j++) f[i][j] = f[i - 1][j];
	for (int j = a[i]; j <= m; j++) f[i][j] = (f[i - 1][j] + f[i - 1][j - a[i]]) % mod;
}

for (int i = 1; i <= n; i++)
{
	for (int j = 0; j < a[i]; j++) g[i][j] = f[n][j];
	for (int j = a[i]; j <= m; j++) g[i][j] = (f[n][j] - g[i][j - a[i]] + mod) % mod;
}

21点

21点是经典的扑克玩法，玩家的目标是使手中的牌的点数之和不超过21点且尽量大。

你正在游玩一个类似的游戏，共有 $n$ 张牌，点数分别为 $x_1,x_2,\dots ,x_n$ 。

游戏开始时，你手里没有牌。

你可以（多次）选择在剩下的牌中等概率随机抽取一张（可以马上看到抽到的牌的点数，再做决策），或者直接进行结算。在任何时刻，你手中牌的点数之和超过 $R$ 则游戏失败。在结算时，若你手中的牌点数之和超过 $L$ ，则获得游戏胜利，否则也算失败。

在最优策略下，你的获胜概率最多可以达到多少？

$f_{i,j}$ 表示选取 $i$ 张卡片，它们的点数总和为 $j$ 的方案数

$g_{j,k}$ 表示不选第 $i$ 张卡片，选取 $j$ 张卡片，点数总和为 $k$ 的方案数

#include <cstdio>
#include <algorithm>

const int maxn = 500 + 10;

int a[maxn];
double f[maxn][maxn];
double g[maxn][maxn];

int main()
{
	int n, l, r;
	scanf("%d %d %d", &n, &l, &r);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	
	f[0][0] = 1;
	for (int i = 1; i <= n; i++)
	{
		for (int j = i; j >= 1; j--)
		{
			for (int k = 0; k < a[i]; k++) f[j][k] = f[j][k];
			for (int k = a[i]; k <= r; k++) f[j][k] = f[j - 1][k - a[i]] * j / (n - j + 1) + f[j][k];
		}
		f[0][0] = 1;
	}
	
	double ans = 0;
	for (int i = 1; i <= n; i++)
	{
		g[0][0] = 1;
		for (int j = 1; j < n; j++)
		{
			for (int k = 0; k < a[i]; k++) g[j][k] = f[j][k];
			for (int k = a[i]; k <= r; k++) g[j][k] = f[j][k] - g[j - 1][k - a[i]] * j / (n - j + 1);
		}
		
		for (int s = std::max(l - a[i] + 1, 0); s <= std::min(r - a[i], l); s++)
		{
			for (int j = 0; j < n; j++)
			{
				ans += g[j][s] / (n - j);
			}
		}
	}
	printf("%.12lf\n", ans);
	return 0;
}