线性DP
例题1：Tak and Cards AtCoder ARC060A Tak and Cards
有 \(n\) 个整数。第 \(i\) 个数的值为 \(x_i\) 。
从这些整数中挑选 \(1\) 个及以上，使选择的整数的平均数等于 \(A\) ，有多少种方案。
状态：\(f[i][j][k]\) ：在前 \(i\) 个数中选取 \(j\) 个数，累加和为 \(k\) 的方案数
状态转移：\(f[i][j][k]=f[i-1][j][k]+f[i-1][j-1][k-x[i]]\)
f[0][0][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=i;j++)
{
for(int k=0;k<=sum[i];k++)
{
if(j>=1&&k>=x[i]) f[i][j][k]=f[i-1][j][k]+f[i-1][j-1][k-x[i]];
else f[i][j][k]=f[i-1][j][k];
}
}
}
输出：
long long ans=0;
for(int i=1;i<=n;i++)
ans+=f[n][i][i*a];
printf("%lld\n",ans);
Tips: 本质还是 01 背包，可以将第一维阶段优化掉。
例题2：货币系统 Luogu P5020 [NOIP2018 提高组]
在网友的国度中共有 \(n\) 种不同面额的货币，第 \(i\) 种货币的面额为 \(a[i]\)，你可以假设每一种货币都有无穷多张。为了方便，我们把货币种数为 \(n\)、面额数组为 \(a[1..n]\) 的货币系统记作 \((n,a)\) 。
在一个完善的货币系统中，每一个非负整数的金额 \(x\) 都应该可以被表示出，即对每一个非负整数 \(x\)，都存在 \(n\) 个非负整数 \(t[i]\) 满足 \(a[i] \times t[i]\) 的和为 \(x\)。然而， 在网友的国度中，货币系统可能是不完善的，即可能存在金额 \(x\) 不能被该货币系统表示出。例如在货币系统 \(n=3\), \(a=[2,5,9]\) 中，金额 \(1,3\) 就无法被表示出来。
两个货币系统 \((n,a)\) 和 \((m,b)\) 是等价的，当且仅当对于任意非负整数 \(x\)，它要么均可以被两个货币系统表出，要么不能被其中任何一个表出。
现在网友们打算简化一下货币系统。他们希望找到一个货币系统 \((m,b)\)，满足 \((m,b)\) 与原来的货币系统 \((n,a)\) 等价，且 \(m\) 尽可能的小。他们希望你来协助完成这个艰巨的任务：找到最小的 \(m\) 。
分析：
简化原题：一个集合的元素可以通过累加表示出来的数，能否用另一个包含元素个数最小的集合表示出来。
把货币系统 \((n,a)\) 看做集合 \(A\) ，货币系统 \((m,b)\) 看做集合 \(B\) 。根据题意，\(B\subseteq A\) 。
那么，只需要计算出 \(A\) 集合中存在多少个能被其它数组成的数计算出来就行了。
即：可行性完全背包。
状态：\(f[i][j]\) ：集合 \(A\) 中前 \(i\) 小的数能否组成面额为 \(j\) 的货币
状态转移： \(f[i][j]=f[i-1][j]|f[i-1][j-a[i]]\)
Tips: 完全背包可以将第一维阶段优化掉。
sort(a+1,a+1+n);
f[0]=1; ans=n;
for(int i=1;i<=n;i++)
{
if(f[a[i]])
{
ans--;
continue;
}
for(int j=a[i];j<=a[n];j++)
f[j]|=f[j-a[i]];
}
printf("%d\n",ans);
例题3：挂饰 Luogu P4138 [JOISC2014]
JOI 君有N个装在手机上的挂饰，编号为 \(1...N\) 。 JOI 君可以将其中的一些装在手机上。
JOI 君的挂饰有一些与众不同——其中的一些挂饰附有可以挂其他挂件的挂钩。每个挂件要么直接挂在手机上，要么挂在其他挂件的挂钩上。直接挂在手机上的挂件最多有 \(1\) 个。
此外，每个挂件有一个安装时会获得的喜悦值，用一个整数来表示。如果JOI君很讨厌某个挂饰，那么这个挂饰的喜悦值就是一个负数。
JOI 君想要最大化所有挂饰的喜悦值之和。注意不必要将所有的挂钩都挂上挂饰，而且一个都不挂也是可以的。
分析：
挂饰必须挂在挂钩上，手机上可以直接挂一个挂饰。
对于物品可以分成四类：
- 有挂钩，装饰度非负
- 有挂钩，装饰度为负数
- 无挂钩，装饰度非负
- 无挂钩，装饰度为负数
可见对于第 \(1\) 种拿取是最优的，对于第 \(4\) 种不拿是最优的，那么就只剩 \(、2、3\) 两种需要判断了。
对于第 \(2\) 种物品，可以用 \(f[i]\) 表示当还有 \(i\) 个剩余挂钩时的最大装饰度，做一次 01背包 即可求 \(f\) 数组。
对于第 \(3\) 种物品，只要拿价值最大的就可以了， 那么降序排序后的前缀和 \(s[i]\) 就可以表示当挂钩数为 \(i\) 时的最大装饰度。
那么答案就是 \(max(f[i]+s[i])\) 了，注意还要加上第 \(1\) 种物品给答案的贡献。
挂钩的个数对后续选择物品有正向作用。我们先按物品的挂钩个数从大到小排序。
然后就可以做背包，挂钩的个数当体积。
但是加了物品，体积会增加，此方法不可行，因此使用二维状态。
状态：\(f[i,j]\) 表示挂好了前 \(i\) 个物品，剩余 \(j\) 个钩子还未使用时的最大喜悦值
状态转移：
\[当 a[i].x\geq j时，f[i][j]=max(f[i-1][1]+a[i].val,f[i-1][j]);\\ 当 a[i].x < j 时，f[i][j]=max(f[i-1][j],f[i-1][j-a[i].x+1]+a[i].val);\\ \]memset(f,-100,sizeof(f));
f[0][1]=0;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=n;j++)
{
if(a[i].x>=j) f[i][j]=max(f[i-1][1]+a[i].val,f[i-1][j]);
else f[i][j]=max(f[i-1][j],f[i-1][j-a[i].x+1]+a[i].val);
}
}
输出：
for(int i=0;i<=n;i++)
ans=max(ans,f[n][i]);
printf("%d\n",ans);
例题4：跳跃的Tak AtCdoer ABC179D Leaping Tak
从左到右有 \(N\) 个连续排列的编号为$ 1,2,⋯,N$ 的房间。
Tak 目前在房间 \(1\) 中。他正尝试通过使用以下描述的步骤到达房间 \(N\) 。
给你一个小于等于 \(10\) 的整数 \(K\) ，以及 \(K\) 个不相交的段 \([L_1,R_1],[L_2,R_2],⋯,[L_K,R_K]\) 。
令 \(S\) 为这 \(K\) 个段的并集。 在此，段 \([l,r]\) 表示由满足 \(l \leq i \leq r\) 的所有整数 \(i\) 组成的集合。
在房间 \(i\) 中时，从 \(S\) 中选择一个整数 \(d\) 并移至房间 \(i+d\) 。你不能移出这些房间。
为了帮助 Tak ，请找到前往房间 \(N\) 的方案数对 \(998244353\) 取模的结果。
暴力：
状态：\(f[i]\) 表示到达第 \(i\) 个点的方案数
状态转移：\(dp[i] = dp[i-l] +dp[i-l-1]+ \cdots +dp[i-r]\)
f[1]=1;
for(int i=2;i<=n;i++)
for(int j=1;j<=k;j++)
for(int k=l[j];k<=r[j];k++)
f[i]=(f[i]+f[i-k])%998244353;
printf("%lld\n",f[n]);
前缀和：
区间不相交，不存在重合，枚举每个区间，用前缀和来状态转移。
f[1]=1; sum[1]=1;
for(int i=2;i<=n;i++)
{
for(int j=1;j<=k;j++)
f[i]=(f[i]+sum[max(0,i-l[j])]-sum[max(0,i-r[j]-1)]+998244353)%998244353;
sum[i]=(sum[i-1]+f[i])%998244353;
}
printf("%lld\n",f[n]);
例题5：逆序对数列个数 Luogu P2513 [HAOI2009] 逆序对数列
对于一个数列 \(\{a_i\}\)，如果有 \(i<j\) 且 \(a_i>a_j\)，那么我们称 \(a_i\) 与 \(a_j\) 为一对逆序对数。若对于任意一个由 \(1 \sim n\) 自然数组成的数列，可以很容易求出有多少个逆序对数。那么逆序对数为 \(k\) 的这样自然数数列到底有多少个？
状态：\(f[i]\)表示前 \(i\) 个数组成逆序对个数为 \(j\) 的全排列的方案个数
状态转移：
\[f[i][j]=\sum _{k=0} ^{min(i-1,j)} f[i-1][j-k] = \sum _{k=max(0,j-i+1)} ^j f[i-1][k] \]f[1][0]=1;
for(int i=2;i<=n;i++)
{
int sum=0;
for(int j=0;j<=k;j++)
{
sum=(sum+f[i-1][j])%10000;
f[i][j]=sum;
if(j-i+1>=0) sum=(f[i][j]-f[i-1][j-i+1])%10000;
}
}
printf("%lld\n",f[n][k]);
时间复杂度为 \(O(nk^2)\) ，会TLE，优化方法如下：
举个例子，打表如下：
\(f[5][6]=f[4][6]+f[4][5]+f[4][4]+f[4][3]+f[4][2];\)
\(f[5][7]=f[4][7]+f[4][6]+f[4][5]+f[4][4]+f[4][3];\)
\(f[5][8]=f[4][8]+f[4][7]+f[4][6]+f[4][5]+f[4][4];\)
由表可知，\(f[i][j]=f[i][j-1]+f[i-1][j]-f[i-1][j-i+1]\) 。
利用前缀和思想，类似双指针维护状态转移，时间复杂度为 \(O(nk)\)：
f[1][0]=1;
for(int i=2;i<=n;i++)
{
int sum=0;
for(int j=0;j<=k;j++)
{
sum=sum+f[i-1][j];
f[i][j]=sum%10000;
if(j-i+1>=0) sum=sum-f[i-1][j-i+1];
}
}
printf("%d\n",f[n][k]);
例题6：整数划分1 51Nod1201 整数划分
将 \(N\) 分为若干个不同整数的和，有多少种不同的划分方式。
例如：\(n = 6\)，\(\{6\} ,\{1,5\}, \{2,4\} ,\{1,2,3\}\)，共 \(4\) 种。
由于数据较大，输出 \(Mod \ 10^9 + 7\) 的结果即可。
状态： \(f[i][j]\)：使用前 \(i\) 个数字，累加和为 \(j\) 的方案数
状态转移： \(f[i][j]=f[i-1][j]+f[i-1][j-i]\)
本质上是 01背包，时间复杂度为 \(O(n^2)\)，会TLE，优化方法如下：
\(n\) 最大是 \(50000\)，最多能由不到 \(320\) 个不同的数字构成，能够确定所用数字的上界。
因此可以采用不同的数字作为阶段：
状态：\(f[i][j]\)：用 \(i\) 个不同正整数构成 \(j\) 的方案数
状态转移：\(f[i][j]=f[i][j-i]+f[i-1][j-i]\)
- \(f[i][j-i]\) 表示用 \(i\) 个不包括 \(1\) 的数构成 \(j\) 的方案数（\(j-i\) 是因为给选出来的 \(i\) 个数都 \(+1\)，共 \(+i\)）
- \(f[i-1][j-i]\) 表示用 \(i\) 个包括 \(1\) 的数构成 \(j\) 的方案数（\(j-i\) 同理，\(i-1\) 是因为 \(+1\) 之后有一个数字为 \(1\)，那么原数字有一个为 \(0\)，而 \(i\in \mathbb N ^+\)， 故只有 \(i-1\) 个数）
f[0][0]=1;
for(int i=1;i*i<=(n<<1);i++)
for(int j=i;j<=n;j++)
f[i][j]=(f[i-1][j-i]+f[i][j-i])%MOD;
for(int i=1;i*i<=(n<<1);i++)
ans=(ans+f[i][n])%MOD;
printf("%d\n",ans);
例题7：乌龟棋 Luogu P1541 [NOIP2010 提高组]
乌龟棋的棋盘是一行\(N\)个格子，每个格子上一个分数（非负整数）。棋盘第1格是唯一的起点，第\(N\)格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。
乌龟棋中\(M\)张爬行卡片，分成4种不同的类型（\(M\)张卡片中不一定包含所有\(4\)种类型的卡片，见样例），每种类型的卡片上分别标有\(1,2,3,4\)四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。
游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。
很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小明想要找到一种卡片使用顺序使得最终游戏得分最多。
现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到多少分吗？
状态：\(dp[i1][i2][i3][i4]\)：第一种牌取了 \(i1\) 张，第二种牌取了 \(i2\) 张，第三种牌取了 \(i3\) 张，第四种牌取了 \(i4\) 张
状态转移：
\(sum=a[1+1\times i1+\times *i2+3\times i3+4\times i4];\)
\(当i1\neq 0时，f[i1][i2][i3][i4]=max(f[i1][i2][i3][i4],f[i1-1][i2][i3][i4]+sum);\)
\(当i2\neq 0时，f[i1][i2][i3][i4]=max(f[i1][i2][i3][i4],f[i1][i2-1][i3][i4]+sum);\)
\(当i3\neq 0时，f[i1][i2][i3][i4]=max(f[i1][i2][i3][i4],f[i1][i2][i3-1][i4]+sum);\)
\(当i4\neq 0时，f[i1][i2][i3][i4]=max(f[i1][i2][i3][i4],f[i1][i2][i3][i4-1]+sum);\)
f[0][0][0][0]=a[1];
for(int i1=0;i1<=a1;i1++)
for(int i2=0;i2<=a2;i2++)
for(int i3=0;i3<=a3;i3++)
for(int i4=0;i4<=a4;i4++)
int sum=a[1+1*i1+2*i2+3*i3+4*i4];
if(i1!=0) f[i1][i2][i3][i4]=max(f[i1][i2][i3][i4],f[i1-1][i2][i3][i4]+sum);
if(i2!=0) f[i1][i2][i3][i4]=max(f[i1][i2][i3][i4],f[i1][i2-1][i3][i4]+sum);
if(i3!=0) f[i1][i2][i3][i4]=max(f[i1][i2][i3][i4],f[i1][i2][i3-1][i4]+sum);
if(i4!=0) f[i1][i2][i3][i4]=max(f[i1][i2][i3][i4],f[i1][i2][i3][i4-1]+sum);
printf("%d\n",f[a1][a2][a3][a4]);
例题8：正整数分组 51Nod1007
将一堆正整数分为 \(2\) 组，要求 \(2\) 组的和相差最小。
状态：\(f[i][j]\)：把前 \(i\) 个数分成 \(2\) 组，差为 \(j\) 是否可行
状态转移：
\(f[i][j]|=f[i-1][j+a[i]];\)
\(当j-a[i]\geq 0时，f[i][j]|=f[i-1][j-a[i]];\)
\(当a[i]-j\geq 0时，f[i][j]|=f[i-1][a[i]-j];\)
- 把 \(a[i]\) 放入了和较小的那组，和较小的依然是较小的那组
- 把 \(a[i]\) 放入了和较大的那组，和另外一组差更大
- 把 \(a[i]\) 放入了和较小的那组，变为较大的一组
f[0][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=sum;j++)
{
f[i][j]|=f[i-1][j+a[i]];
if(j-a[i]>=0) f[i][j]|=f[i-1][j-a[i]];
if(a[i]-j>=0) f[i][j]|=f[i-1][a[i]-j];
}
}
输出：
for(int i=0;i<=sum;i++)
{
if(f[n][i])
{
printf("%d\n",i);
break;
}
}
例题9：构建双塔 Luogu P1651 塔
小明很喜欢摆积木，现在他正在玩的积木是由 \(N\) 个木块组成的，他想用这些木块搭出两座高度相同的塔。
一座塔的高度是搭建它的所有木块的高度和，并且一座塔至少要用一个木块。
每个木块只能用一次，也可以不用，目前已知每块木块的高度。
小明想知道在最终两个塔的高度相同的情况下，他所能搭的塔的最大高度是多少。
状态：\(f[i][j]\)表示取前 \(i\) 块积木、两塔差为 \(j\) 时较高塔的最大高度
状态转移：
\(f[i][j]=max(f[i-1][j],f[i-1][j+a[i]]);\)
\(当j-a[i]\geq 0时，f[i][j]=max(f[i][j],f[i-1][j-a[i]]+a[i]);\)
\(当a[i]-j\geq 0时，f[i][j]=max(f[i][j],f[i-1][a[i]-j]+j);\)
- 丢掉了第 \(i\) 块积木
- 把 \(a[i]\) 放入了高度较大的那组，两组高度差 \(+a[i]\)
- 把 \(a[i]\) 放入了和较小的那组，变为较大的一组，两组高度差 \(+j\)
memset(f,-10,sizeof(f));
f[0][0]=0;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=sum;j++)
{
f[i][j]=max(f[i-1][j],f[i-1][j+a[i]]);
if(j-a[i]>=0) f[i][j]=max(f[i][j],f[i-1][j-a[i]]+a[i]);
if(a[i]-j>=0) f[i][j]=max(f[i][j],f[i-1][a[i]-j]+j);
}
}
输出：
if(f[n][0]!=0) printf("%d\n",f[n][0]);
else printf("Impossible\n");
例题10：关灯问题 Vijos1488 路灯的改建计划
小x 同学仔细了解每盏路灯的耗电量 \(a[i]\) 与照明度 \(z[i]\)，已知共有 \(N\) 盏电灯，并且每盏电灯都可能有不同的耗电量与照明度。
现在的问题是要把这 \(N\) 盏电灯分为 \(M\) 组，新分出的每组灯的耗电量（即是该组所有打开电灯的耗电量之和）不能超过该组的电灯数目的 \(T\) 倍，在满足这样的前提下使得照明度尽可能的大，最后算出 \(M\) 组的最大照明度的和。
由于每组耗电量的限制，该组中的某些电灯可能不被使用，但是仍然应该算作该组灯的数目。
特别注意的是电灯按顺序给出，只能把相邻的几盏灯分在一组。
分析：
本题核心问题在于如何分组，相当于是在一定限制条件下将一些点分进若干个集合里。
现在考虑加入第 \(i\) 盏灯，如果先不管此灯的开关情况，结果有两种：
- 放入一个空的集合里面
- 放入上一盏灯所在的集合
但由于并不知道上一个集合的左端点在哪里，所以要枚举。
状态：\(f[i][j]\)：前 \(i\) 盏灯放进 \(j\) 个集合的最优值
\(g[x][y]\)：将区间 \([x,y]\) 内的灯放入一个集合时，该集合能得到的最大亮度
状态转移：\(f[i][j]=max(f[i][j],f[i-k][j-1]+g[i-k+1][i])\)
for(int i=1;i<=n;i++)
{
for(int j=1;j<=min(i,m);j++)
{
int sum=0;
for(int k=1;k<=i-j+1;k++)
sum=max(sum,f[i-k][j-1]+g[i-k+1][i]);
f[i][j]=sum;
}
}
printf("%d\n",f[n][m]);
初始化：
\(g[i][j]\) 为 01背包 问题
for(int i=1;i<=n;i++)
{
memset(dp,0,sizeof(f));
int c=(n-i+1)*t;
for(int j=i;j<=n;j++)
{
for(int k=c;k>=a[j];k--)
dp[k]=max(dp[k],dp[k-a[j]]+b[j]);
g[i][j]=dp[(j-i+1)*t];
}
}