DP/动态规划算法
sdxjzsq
2020-04-19 12:40:57
# 背景
颓废了大半个月了...
自从脑洞程序设计周开始ACM的状态就开始断崖式变差...除了题目经常没思路之外，诸如多组输出忘记换行、输出带提示词等的低级错误也时有发生。
特别第三次DP训练直接就上演最后一次提交超时30s，赛后连A两题的传统艺能。不过总归要比做不出来要好，毕竟之前DP水平拜高中教练给我打印的两大本DP题所赐还是不错的。
# 更新日志
5/11 第九次训练题目：
D. CF721C Journey
I. CF1312E Array Shrinking(区间DP)
J. CF730J Bottles(01背包)
5/10 第八次训练题目：
A. CF461B Appleman and Tree(树形DP)
C. HDU2196 Computer(树形DP)
F. CF16E Fish(概率DP)
H. HDU4336 Card Collector(期望DP)
5/7 第七次训练题目：
C. HDU2089 不要62(数位DP)
E. UVA12670 Counting ones(数位DP)
F. POJ2228 Naptime(环形DP)
4/26 第六次训练题目：
A. UVA10817 Headmaster's Headache(状压DP)
B. UVA11825 Hackers' Crackdown(状压DP)
4/23 第五次训练题目：
C. HDU5119 Happy Matt Friends(~~状压DP，~~计数DP)
4/19 第四次训练题目：
B. HDU4745 Two Rabbits(区间DP)
4/16 第三次训练题目：
A. UVA 10534 Wavio Sequence(LIS)
H. LightOJ 1248 Dice (III)(概率DP)
# OI时期总结的注意点
1. 不开long long见祖宗，十年OI一场空
2. 01背包对于价值的枚举边界最小值是每个物品的最小值，而不能换成别的，如果换成最小的物品价值，就会RE,即使不RE也会WA...
3. 当题目中有三个量，而一种转移方式`dp[i][j]=k`不能满足要求的时候，试试另一种转移方式：`dp[i][k]=j`。
# LIS（最长上升子序列）
## 算法思想
令$d[i]$表示前i个元素的最长上升子序列的长度，那么DP方程为：
$d[i]=max\{d[k]+1\},k<i$且$a[k]<a[i]$
但是，如果直接去计算，复杂度是$O(n^2)$的，因此我们需要一种方法快速找出$1\cdots i-1$中满足$a[k]<a[i]$的最大的$d[k]$的值，反过来说，在d值相同的情况下，a值只需要保留最小的，这样只要在最小的这些$a[i]$中找到最接近$a[i]$的一个，$d[k]$一定是最大的。
因此用$g[i]$表示d值为i的数的a的最小值，即$g[i]=min\{a[k]\}$且$d[k]=i$，显然$g$是单调递增的。
这样，状态转移更新$d[i]$，就可以直接在$g$中找到大于等于$a[i]$的第一个数$g[j]$，则$d[i]=j$，同时更新$g[j]=a[i]$。
因为$g$数组是单调递增的，因此珂以用lower_bound算法二分查找。总复杂度$O(nlogn)$
## 核心代码
``` cpp
memset(g,0x3f,sizeof(g));//fill(g+1,g+n+1,inf);//这个也可
for(register int i=1;i<=n;i++)d[i]=lower_bound(g+1,g+n+1,a[i])-g,g[d[i]]=a[i];
```
## UVA 10534 Wavio Sequence
### 题目链接
https://www.luogu.com.cn/problem/UVA10534
https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1475
### 题目大意
在给定序列中寻找最长的子序列满足：
1. 长度为$2\times l+1$
2. 前$l+1$为严格递增序列，后$l+1$为严格递减序列
### 思路
直接正反两遍LIS板子，然后枚举中点的位置即可。
### code
```cpp
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 10005;
int n,a[maxn],b[maxn],g[maxn],d[maxn],f[maxn],ans;
int main()
{
while(scanf("%d",&n)!=EOF)
{
ans=0;
for(register int i=1;i<=n;i++)scanf("%d",&a[i]),b[n-i+1]=a[i];
memset(g,0x3f,sizeof(g));
for(register int i=1;i<=n;i++)
{
d[i]=lower_bound(g+1,g+n+1,a[i])-g;
g[d[i]]=a[i];
}
memset(g,0x3f,sizeof(g));
for(register int i=1;i<=n;i++)
{
f[i]=lower_bound(g+1,g+n+1,b[i])-g;
g[f[i]]=b[i];
}
for(register int i=1;i<=n;i++)
ans=max(ans,min(d[i],f[n-i+1]));
printf("%d\n",(ans<<1)-1);
}
return 0;
```
# 区间DP
## 算法思想
区间DP一般分为两种形式，一种是区间合并求最小费用，例如合并石子；另一种是在不断扩大区间求值，例题如下。
## HDU4745 Two Rabbits
### 题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=4745
### 题目大意
两只兔子分别从环上的某点开始，一个顺时针跳，一个逆时针跳，要求两只兔子所站的数字总是相同的，且两只兔子不能跳过或跳到起点。求最多能跳多少次。
### 思路
本题珂以转化为求环上的最长回文子序列（复杂度不明，搜索了一下其他博客也都是直接就说出来了，没有找到正确性证明...）
设$dp[l][r]$表示$a[l]$到$a[r]$间最长回文子序列长度，则DP转移方程为：
$$
dp[l][r]=\begin{cases}max\{dp[l+1][r],dp[l][r-1]\}&a[l]\neq a[r],\\max\{dp[l+1][r],dp[l][r-1],dp[l+1][r-1]+2\}&a[l]=a[r]\end{cases}
$$
本题比较特殊，是在环上求最长回文子序列，而不是区间上，因此有两种方式解决：
1. 将环复制一遍，在倍增后的区间上做动态规划，则答案为所有长度为$n$的区间最长回文子序列长度的最大值。
这种做法下，因为是环，所以起点珂以不在回文子序列中，因此在计算答案的时候需要求长度为$n$的区间值和长度为$n-1$的区间值+1中的最大值。
2. 一个环上的最长回文子序列，也珂以转化为两个不相交回文子序列的并。比如一个环为：`1 2 3 4 3 2 1`（最长回文子序列就是本身）珂以看成回文子序列`2 1 1 2`和`3 4 3`的并；第一种算法的特殊情况，其实就是长度为1的回文子序列和长度为$n-1$的回文子序列的并。
因此不用倍增，只计算两个不相交的回文子序列长度和的最大值即可。
### 代码
算法一：
``` cpp
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 2005;
int n,a[maxn],dp[maxn][maxn],t,ans;
int main()
{
while(scanf("%d",&n),n)
{
t=n<<1,ans=0;
for(register int i=1;i<=n;i++)scanf("%d",&a[i]),a[i+n]=a[i],dp[i][i]=1;
for(register int l=1;l<=n;l++)
for(register int i=1;i+l<=t;i++)
{
dp[i][i+l]=max(dp[i+1][i+l],dp[i][i+l-1]);
if(a[i]==a[i+l])dp[i][i+l]=max(dp[i+1][i+l-1]+2,dp[i][i+l]);
}
for(register int i=1;i+n-1<=t;i++)ans=max(ans,max(dp[i][i+n-2]+1,dp[i][i+n-1]));
printf("%d\n",ans);
}
return 0;
}
```
算法二：
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1005;
int n,a[maxn],dp[maxn][maxn],ans;
int main()
{
while(scanf("%d",&n),n)
{
for(register int i=1;i<=n;i++)scanf("%d",&a[i]),dp[i][i]=1;ans=0;
for(register int k=1;k<n;k++)
for(register int i=1;i+k<=n;i++)
{
dp[i][i+k]=max(dp[i+1][i+k],dp[i][i+k-1]);
if(a[i]==a[i+k])dp[i][i+k]=max(dp[i][i+k],dp[i+1][i+k-1]+2);
}
for(register int i=0;i<=n;i++)ans=max(ans,dp[1][i]+dp[i+1][n]);
printf("%d\n",ans);
}
return 0;
}
```
## CF1312E Array Shrinking
### 题目链接
https://www.luogu.com.cn/problem/CF1312E
https://codeforces.com/problemset/problem/1312/E
### 题目大意
已知一个数组，每次可以选择数列中相邻且相等的数字合并，合并后替换为原数+1，问数组经过若干次合并后的最小长度。
### 思路
不看题解完全没想到珂以用区间dp...
令$dp[i][j][0/1]$表示区间$[i,j]$合并后的最小长度/合并后最右侧的数字，则得到$dp$转移方程为：
$$
dp[i][j]=\begin{cases}
1,dp[i][k][1]+1,&dp[i][k][0]=dp[k+1][j][0]=1\&dp[i][k][1]=dp[j][k+1][1]\\
dp[i][k][0]+dp[k+1][j][0],dp[k+1][j][1],&dp[i][k][0]+dp[k+1][j][0]<dp[i][j][0]
\end{cases}
$$
### code
``` cpp
#include<cstdio>
#include<cstring>
const int maxn = 505;
int n,dp[maxn][maxn][2];
int main()
{
scanf("%d",&n);
memset(dp,0x3f,sizeof(dp));
for(register int i=1;i<=n;++i)scanf("%d",&dp[i][i][1]),dp[i][i][0]=1;
for(register int k=1;k<n;++k)
for(register int i=1;i+k<=n;++i)
for(register int j=i+1;j<=i+k;j++)
if(dp[i][j-1][0]==1&&dp[j][i+k][0]==1&&dp[i][j-1][1]==dp[j][i+k][1])
dp[i][i+k][0]=1,dp[i][i+k][1]=dp[j][i+k][1]+1;
else if(dp[i][j-1][0]+dp[j][i+k][0]<dp[i][i+k][0])
dp[i][i+k][0]=dp[i][j-1][0]+dp[j][i+k][0],dp[i][i+k][1]=dp[j][i+k][1];
printf("%d",dp[1][n][0]);
return 0;
}
```
# 状压DP
## 算法思想
状态压缩动态规划是动态规划的一种常见优化方法，一般是状态比较多，开成数组维度会很多或者会超空间，因此将状态压缩成一维的一个整数中，加快速度。
## 常用方法
1. 因为压缩会涉及到很多二进制位运算的方法，因此加个链接：[C++位运算及其应用](https://www.luogu.com.cn/blog/xjzsq/c-wei-yun-suan-ji-ji-ying-yong)，文章最下方为状压DP中的常用方法。
2. 枚举某个状态S的子集（S不为全1序列）：
``` cpp
for(int i=S;i;i=(i-1)&S){/*do something...*/}
```
## UVA10817 Headmaster's Headache
### 题目链接
https://www.luogu.com.cn/problem/UVA10817
https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1758
### 题目大意
已知s个科目，学校已经有m个老师，现在有n个老师珂以被聘用，已知所有老师的工资数和会教的科目（每个老师都教至少一个科目），现要求每个科目至少有两个老师教，求工资的最小花费。
### 思路
看到$s\le 8$差不多就知道是状压DP了，但是这个题目比较特殊的地方在于，对于每个科目来说有三个状态——没人教、1个人教和2个以上的人教，二进制的状态压缩就不适用了，需要至少三进制的状态，下面为了方便，我用了四进制。
状态S是一个最多八位的四进制数，每一位上0代表没有人教，1代表有一个人教，2代表有两个以上的人教，3空置不用，因此S不可能出现3（在枚举状态的时候需要注意提前通过判断枚举的状态的某一位上是否有3来排除不存在的状态）。比如，现在有三个科目，科目一有1个人教，科目二有两个人教，科目三没有人交，那么对应的四进制数就是$021$。
那么，令$dp[i][S]$表示前$i$个人中能够使状态为$S$的最小工资花费，$S_i$表示第i个人会教科目对应的四进制数，$S\cup S_i$表示在满足状态含义的情况下的并，$w[i]$表示聘用第i个老师所需的工资，那么得到DP方程为：
$$
dp[i][S\cup S_i]=min\{dp[i-1][S\cup S_i],dp[i-1][S]+w[i]\}
$$
时间复杂度$O(n\times 4^s)$
另外，本题并没有输入每个老师教多少科，所以需要特殊处理一下。
P.S. 这个题调了大概一周，最后走投无路写了个对拍拍了几十组小数据才拍出来问题，附上小数据生成器：
``` cpp
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cstring>
using namespace std;
inline int getr(int o){return rand()%o+1;}
inline int getlr(int l,int r)
{
int ans=getr(r);
while(ans<l)ans=getr(r);
return ans;
}
int a[10],oo;
int main()
{
srand(time(0));
int s=getr(4),m=getr(10),n=getr(10);
printf("%d %d %d\n",s,m,n);
for(register int i=1;i<=m;i++)
{
printf("%d ",getlr(10000,50000));
int ppp=getr(s);
memset(a,0,sizeof(a));
oo=-1;
while(ppp--)
{
if(oo!=-1)printf("%d ",oo);
oo=getr(s);
while(a[oo])oo=getr(s);
a[oo]=1;
}
printf("%d\n",oo);
}
for(register int i=1;i<=n;i++)
{
printf("%d ",getlr(10000,50000));
int ppp=getr(s);
memset(a,0,sizeof(a));
oo=-1;
while(ppp--)
{
if(oo!=-1)printf("%d ",oo);
oo=getr(s);
while(a[oo])oo=getr(s);
a[oo]=1;
}
printf("%d\n",oo);
}
printf("0 0 0\n");
return 0;
}
```
### code
``` cpp
#include<cstdio>
#include<algorithm>
#include<cstring>
#include <iostream>
#include <cstdlib>
using namespace std;
const int maxn = 105;
int s,m,n,mc,ms[10],nc[maxn],ns[maxn][10],s0,s1;
long long dp[maxn][1<<18];
char ss[105];
inline void trans()
{
int i=0;
while(ss[i]!='\0')
{
if(ss[i]<'0'||ss[i]>'9')i++;
else ms[ss[i]-'0']++,i++;
}
return;
}
inline void tran(int o)
{
int i=0;
while(ss[i]!='\0')
{
if(ss[i]<'0'||ss[i]>'9')i++;
else ns[o][++ns[o][0]]=ss[i]-'0',i++;
}
return;
}
inline bool check(int S)
{
while(S)
{
if((S&1)&&((S>>1)&1))return false;
S>>=2;
}
return true;
}
inline int cha(int S,int o)
{
for(register int i=1;i<=ns[o][0];i++)
{
int tmp = S>>((ns[o][i]-1)<<1);tmp%=4;
if(tmp<2)S+=1<<((ns[o][i]-1)<<1);
}
return S;
}
int main()
{
while(scanf("%d%d%d",&s,&m,&n),s)
{
memset(dp,0x3f,sizeof(dp));
memset(ns,0,sizeof(ns));
memset(ms,0,sizeof(ms));
int x;mc=s0=s1=0;
for(register int i=1;i<=m;i++)scanf("%d",&x),mc+=x,gets(ss),trans();
for(register int i=1;i<=n;i++)scanf("%d",&nc[i]),gets(ss),tran(i);
for(register int i=s;i>0;i--)s0=(s0<<2)+(ms[i]>2?2:ms[i]),s1=(s1<<2)+2;
dp[0][s0]=mc;
for(register int i=1,tmp;i<=n;i++)
for(register int S=s0;S<=s1;S++)
if(check(S))
dp[i][S]=min(dp[i-1][S],dp[i][S]),tmp=cha(S,i),dp[i][tmp]=min(dp[i][tmp],min(dp[i-1][tmp],dp[i-1][S]+nc[i]));
printf("%lld\n",dp[n][s1]);
}
return 0;
}
```
## UVA11825 Hackers' Crackdown
### 题目链接
https://www.luogu.com.cn/problem/UVA11825
https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=226&page=show_problem&problem=2925
### 题目大意
将$n$个集合分成尽量多组，使得每一组里面所有集合的并集等于全集。
### 思路
令dp[i]表示i代表的子集能够组成的全集个数，其中i是一个二进制数，从右往左第k位表示第k个集合是否被选择；j是状态i的子集；$check(i)$表示i代表的子集是否能构成全集（返回1/0）。
那么DP方程为：
$$
dp[i]=max\{dp[i\hat{\,\,\,}j]+check(j)\},j\subseteq i
$$
此外，因为同一个j的check(j)会被使用多次，所以需要预处理，否则会T。
### code
```cpp
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 25;
int n,m,s[maxn],x,dp[1<<17],top,cover[1<<17],A;
inline int check(int S)
{
int now=0;
for(register int i=0;i<n;i++)
{
if((1<<i)&S)now|=s[i];
if(now==A)return 1;
}
return 0;
}
int main()
{
while(scanf("%d",&n),A=(1<<n)-1,n)
{
for(register int i=0;i<n;i++)
{
s[i]=1<<i;
scanf("%d",&m);
while(m--)scanf("%d",&x),s[i]|=1<<x;
}
for(register int i=1;i<=A;i++)cover[i]=check(i),dp[i]=0;
for(register int i=0;i<=A;i++)
for(register int j=i;j;j=(j-1)&i)
if(cover[j])dp[i]=max(dp[i],dp[i^j]+1);
printf("Case %d: %d\n",++top,dp[A]);
}
return 0;
}
```
## HDU5119 Happy Matt Friends
### 题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=5119
### 题目大意
在$n$个数中选出若干个数，使得这些数的异或不小于$m$，求满足条件的选择方案个数
### 思路
本题属于计数DP，状态比较难想（赛后想出来写题解的时候发现又忘了...）
令dp[i][j]表示前$i$个数中，异或结果为$j$的方案数，得到DP方程为：
$$
dp[i][j]=dp[i-1][j]+dp[i-1][j\hat{\,\,\,}a[i]]
$$
本题直接开dp数组会炸空间，所以需要用滚动数组。
你问我这和状压DP有什么关系？其实最开始看到这个题我是想$O(2^n)$枚举子集的，发现n会到40，然后爆了int，枚举子集就算了orz...
### code
``` cpp
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 45,M = 1<<20;
long long n,m,a[maxn],dp[2][M],t,ans,top;
int main()
{
scanf("%lld",&t);
while(t--)
{
scanf("%lld%lld",&n,&m);memset(dp,0,sizeof(dp));ans=0;
for(register int i=1;i<=n;i++)scanf("%lld",&a[i]);
dp[1][0]=1,dp[1][a[1]]=1;
for(register int i=2;i<=n;i++)
for(register int j=0;j<M;j++)
dp[i&1][j]=dp[(i-1)&1][j]+dp[(i-1)&1][j^a[i]];
for(register int i=m;i<M;i++)ans+=dp[n&1][i];
printf("Case #%lld: %lld\n",++top,ans);
}
return 0;
}
```
# 数位DP
## 算法思想
数位DP一般用于统计一段区间中满足要求的数字个数，限制条件一般为数位上不出现某些特定数字等等，因此叫做数位DP。
## 常用方法
一般DP方程的第一维是数字的位数。
通常预处理出题目数据范围内所有符合条件的位数的答案，以加快速度。
## UVA12670 Counting ones
### 题目链接
https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4408
https://www.luogu.com.cn/problem/UVA12670
### 题目大意
统计$l$到$r$的二进制中1的个数。
### 思路
数位DP板子题。
令$dp[i]$表示长度小于等于i位的所有二进制数中1的个数，则
$$
dp[i]=dp[i-1]\times2+2^{i-1}
$$
然后，从最高位开始，如果该位为1，那么比他低一位的所有二进制数都将出现一次，并且，剩下的数最高位都将有1个1，因此对答案的贡献为$dp[i-1]+x-2^{i=1}$($x$为当前的数字，每次计算完某一位对答案的贡献后，都需要将$x$置为$x-2^{i-1}$，因为下一次循环中，剩下的数最高位均为1（并且已经统计），需要去掉这次已经统计的最高位为0的数)，如此枚举直至个位。
P.S. 因为统计的时候统计不到自己，所以传参需要+1.
### code
``` cpp
#include<cstdio>
long long a,b,pos[60],dp[60],cnt,ans,o;
inline long long solve(long long x)
{
for(cnt=ans=0,o=x;o;o>>=1)pos[++cnt]=o&1;
for(register int i=cnt;i>0;--i)if(pos[i])ans+=dp[i-1]+(x-=1ll<<i-1);
return ans;
}
int main()
{
for(register int i=1;i<=60;i++)dp[i]=(dp[i-1]<<1)+(1ll<<i-1);
while(~scanf("%lld%lld",&a,&b))printf("%lld\n",solve(b+1)-solve(a));
return 0;
}
```
## HDU2089 不要62
### 题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=2089
### 题目大意
给定一个区间，求区间中不含62和4的数字个数。
### 思路
本题有两种思路：
1. 暴力打表法
本题数据范围只有1e6，把所有数字都枚举一遍也只有最多5e6（1e6个数，每个数最多判断5位）的数据量，询问的时候用不用前缀和优化都能过...
当时因为是DP专场就没多想，没想到会如此简单...看到网上这个做法的时候惊呆了，毕竟第二种思路debug了一晚上...
2. 数位DP法
令$dp[i][0/1]$表示从各位开始的第i位非6/为6的方案数，可以得到DP方程为：(上面一个去掉4还剩九个数字，所以乘9；下面去掉了62的特殊情况，所以乘8)
$$
\begin{aligned}
dp[i][1]&=(dp[i+1][1]+dp[i+1][0])\times9\\
dp[i][0]&=dp[i+1][1]\times 8+dp[i+1][0]\times 9
\end{aligned}
$$
然后把每一位上的数字单独处理一下，小于这个数的直接dp求解即可。
### code
1.暴力打表法（真的是太短了......）
``` cpp
#include<cstdio>
bool ok[1000005];int l,r,ans;
int main()
{
for(int i=1;i<=1000000;i++)for(int x=i;x;x/=10)if(x%10==4||x%100==62){ok[i]=1;break;}
while(~scanf("%d%d",&l,&r)&&l+r)
{
for(ans=0;l<=r;l++)if(!ok[l])ans++;
printf("%d\n",ans);
}
return 0;
}
```
2.数位DP法
``` cpp
#include<cstdio>
#include<cstring>
using namespace std;
int l,r,pos[10],n,dp[10][2];
inline int count(int x)
{
memset(pos,0,sizeof(pos));
if(x<10)return x<4?x+1:x;
int t=x;n=0;bool flag=false;
while(t)pos[++n]=t%10,t/=10;t=n;
memset(dp,0,sizeof(dp));
for(register int i=0;i<pos[t];i++)if(i!=4)dp[t][i==6]++;
while(--t)
{
if(flag||pos[t+1]==4||(pos[t+1]==2&&pos[t+2]==6))flag=true;
else
{
for(register int i=0;i<pos[t];i++)if(i!=4)dp[t][i==6]++;
if(pos[t+1]==6&&pos[t]>2)dp[t][0]--;
if(t==1&&pos[t]!=4)dp[t][pos[t]==6]++;
if(t==1&&pos[t+1]==6&&pos[t]==2)dp[t][0]--;
}
for(register int i=0;i<=9;i++)
if(i!=4)
{
if(i==2)dp[t][0]+=dp[t+1][0];
else dp[t][i==6]+=dp[t+1][1]+dp[t+1][0];
}
}
return dp[1][1]+dp[1][0];
}
int main()
{
while(~scanf("%d%d",&l,&r)&&(l+r))printf("%d\n",count(r)-count(l-1));
return 0;
}
```
# 环形DP
## 算法思想
环形DP通常与区间DP联系较大，比如石子合并就是破环成链之后进行区间DP，其中破环成链的方法就是复制一边数组，而复制数组也是环形DP的常用方法；但是像POJ2228 Naptime这个题目就不需要复制数组，而是利用其他性质巧妙地解决环形的问题。
## POJ2228 Naptime
### 题目链接
https://www.luogu.com.cn/problem/SP283
http://poj.org/problem?id=2228
### 题目大意
在一天$N$小时选出$B$小时的睡眠时间，给出每个小时体力的恢复值，并且连续的一段睡眠中只在第二小时之后才会恢复体力，求出这$B$小时体力恢复的最大值。特别地，一段睡眠珂以持续到第二天，第二天的前几个小时不会算作新的睡眠时间段，而是算到前一天的睡眠时间段内，因此如果前一天的最后在睡觉，那么后一天第一段睡觉的所有时间都会恢复体力。
### 思路
如果不考虑第二天接续前一天睡眠的情况，那么令$dp[i][j][1/0]$表示前$i$个小时中已经睡眠$j$小时，且第$i$个小时在/不在睡觉的体力恢复最大值，$u[i]$代表第$i$个小时体力的恢复值，那么DP转移方程为：
$$
\begin{aligned}
dp[i][j][0]&=max\{dp[i-1][j][1],dp[i-1][j][0]\}\\
dp[i][j][1]&=max\{dp[i-1][j-1][1]+u[i],dp[i-1][j-1][0]\}
\end{aligned}
$$
现在来考虑第二天接续睡眠的情况。
不难发现，第二天如果接续睡眠，仅仅是第二天的$dp[1][1][1]$会受到影响，也就是初值应该为$u[1]$而不是0，而且此时必须保证前一天的最后一个小时必须处于睡眠状态，也就是这种情况下答案只能是$dp[N][B][1]$。
最后，保留上述两种情况计算出的答案的较大值即可。
### code
``` cpp
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 4005;
int n,b,t,u[maxn],dp[maxn][2],dpa[maxn][2];
int main()
{
for(scanf("%d",&t);t--;)
{
memset(dp,-0x3f,sizeof(dp));memset(dpa,-0x3f,sizeof(dpa));
scanf("%d%d",&n,&b);
for(int i=1;i<=n;++i)scanf("%d",&u[i]);
dp[1][1]=dp[0][0]=dpa[0][0]=0,dpa[1][1]=u[1];
for(int i=2;i<=n;++i)
for(int j=min(b,i);j>0;--j)
dp[j][0]=max(dp[j][1],dp[j][0]),dpa[j][0]=max(dpa[j][1],dpa[j][0]),
dp[j][1]=max(dp[j-1][1]+u[i],dp[j-1][0]),dpa[j][1]=max(dpa[j-1][1]+u[i],dpa[j-1][0]);
printf("%d\n",max(dp[b][0],max(dp[b][1],dpa[b][1])));
}
return 0;
}
```
# 概率DP&期望DP
## 算法思想
本类型题目经常与概率论结合，计算满足某些条件的概率（会用到逆元的知识）或者期望，比如~~邦邦~~抽卡抽出一队四星卡期望需要抽多少次，来衡量欧非X)。
## 常用方法
期望DP一般都是从最终状态向前递推，一般会令$dp[i][j]$表示$i,j$状态下到最终状态的距离（期望），然后得到DP转移方程一般为：($dp[k][j]$表示状态$k$转移到状态$j$的概率,$w[k][j]$为转移花费)
$$
dp[i][j]=\sum (dp[i-1][k]+w[k][j])\times p[k][j]
$$
全部写出来后，如果状态转移没有循环则珂以直接递推求得；如果成环则需要求解线性方程组（目前还没遇到）。
## LightOJ 1248 Dice (III)
### 题目链接
http://lightoj.com/volume_showproblem.php?problem=1248
### 题目大意
掷一个$n$面的骰子，求期望掷多少次能够使$n$个面都出现。
### 思路
令$f[i]$表示掷出$i$面骰子的期望，则有：
$$
f[i+1]=f[i+1]\times\frac{i}{n}+f[i]\times\frac{n-i}{n}+1
$$
化简得：
$$
f[i+1]=f[i]+{n\over n-i}
$$
直接递推计算即可。
P.S.本题虽然也是计算期望，但是没有从最终状态向前推，原因是本题所有面都是一样的，出现的可能性均等，使得状态不再是抽到了哪些面，而是抽到了多少面，这种情况下就不需要从最终状态倒着推了。
同时，这个题目也可以用几何分布来做：
如果已经取到$i$个面，那么一次投掷后，得到一个出现过的面的概率是$i\over n$，得到未出现的面的概率是$n-i\over n$，投掷出一个新面的期望次数便是一个几何分布问题。那么，对于已经投掷出$i$个面，投掷出第$i+1$个面的期望$E(X_i)={1\over p}={n\over n-i}$。（几何分布期望）
那么总期望就是：
$$
E(X)=\sum_{i=0}^{n-1}{n\over n-i}
$$
另外发现忘记几何分布期望是怎么来的了，重新推导了一下：
$$
\begin{aligned}
E(X)&=1\times p+2\times (1-p)\times p+\dots+n\times(1-p)^{n-1}\times p\\
&=p\times[1+2\times (1-p)+\dots+n\times(1-p)^{n-1}]\\
&=p\times f(1-p)\\
\end{aligned}
$$
$$
\begin{aligned}
x\times f(x)&=x+2\times x+\dots+n\times x^n\\
f(x)-x\times f(x)&=1+x+x^2+\dots+x^n\\
(1-x)\times f(x)&=\frac{1-x^n}{1-x}\\
f(x)&=\frac{1-x^n}{(1-x)^2}\\
{\lim_{n \to +\infty}}f(x)&={1\over (1-x)^2}\\
\end{aligned}
$$
$$
\begin{aligned}
E(X)&=p\times f(1-p)\\
&=p\times {1\over [1-(1-p)]^2}\\
&=p\times {1\over p^2}\\
&={1\over p}
\end{aligned}
$$
### code
``` cpp
#include<cstdio>
double ans,n;
int main()
{
for(register int t,x,cnt=scanf("%d",&t);cnt<=t;cnt++)
{
scanf("%d",&x),n=x,ans=0;
while(x--)ans+=n/(n-x);
printf("Case %d: %lf\n",cnt,ans);
}
return 0;
}
```
## HDU4336 Card Collector
### 题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=4336
### 题目大意
卡池中共$n(n\leq20)$种卡，给出每张卡的爆率，期望抽多少次卡能集齐所有卡片。
### 思路
因为本题$n\leq20$，所以很自然地想到状态压缩——把每张卡抽到/没抽到的状态压缩到一个整数中，现在令$dp[S]$表示从状态$S$到目标状态的期望次数，则有：($S+S_i$表示向$S$中增加$i$的状态)
$$
dp[S]=\sum_{i\notin S}\{(dp[S+S_i]+1)\times p[i]\}+(dp[S]+1)\times(1-\sum_{i\notin S}p[i])
$$
化简得：
$$
dp[S]=\frac{1+\sum_{i\notin S}(dp[S+S_i]\times p[i])}{1-\sum_{i\notin S}p[i]}
$$
P.S. 本题是期望DP比较典型的题目，完全符合上面所说的常用方法。
### code
``` cpp
#include<cstdio>
using namespace std;
int n;
double p[25],dp[1<<21],pp;
int main()
{
while(~scanf("%d",&n))
{
p[0]=0;for(register int i=1;i<=n;i++)scanf("%lf",&p[i]),p[0]-=p[i];p[0]+=1;
for(register int S=(1<<n)-2;S>=0;S--)
{
pp=p[0];dp[S]=1;
for(register int i=1;i<=n;i++)
if(S&(1<<i-1))pp+=p[i];
else dp[S]+=dp[S^(1<<i-1)]*p[i];
dp[S]/=1-pp;
}
printf("%.4lf\n",dp[0]);
}
return 0;
}
```
## CF16E Fish
### 题目链接
https://www.luogu.com.cn/problem/CF16E
http://codeforces.com/problemset/problem/16/E
### 题目大意
一群鱼两两相遇概率相等，相遇即互殴致死，给出所有鱼两两相遇后被殴死的概率，计算每条鱼最后存活（只剩最后一条鱼）的概率。
### 思路
这道题$n$的范围只有18，所以必然是状压DP了，令$S$的每一位上0代表鱼已经死亡，1代表鱼还活着，那么$dp[S]$就表示在状态$S$下的概率。
下面来考虑状态转移：($p[j][i]$表示$j$吃掉$i$的概率,$t_S$表示状态$S$中1的个数，即鱼的存活数量)
$$
dp[S]=\sum_{i\notin S}(dp[S+2^{i}]\times\sum_{j\in S}(p[j][i]\times \frac{1}{C_{t_S}^2}))
$$
这个公式中，$dp[S]$只可能由比他多一条鱼的状态$S+2^i$转移而来，而每两条鱼相遇的概率为$\frac{1}{C_{t_S}^2}$，而两个状态之间被干掉的鱼有可能被其他活下来的所有鱼干掉，因此需要求和。珂以看到两条鱼相遇的概率是相等的，因此珂以把$\frac{1}{C_{t_S}^2}$放到求和以后计算。
### code
```cpp
#include<cstdio>
using namespace std;
const int maxn = 20;
double p[maxn][maxn],dp[1<<19];
int n;
int main()
{
scanf("%d",&n),dp[(1<<n)-1]=1;
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
scanf("%lf",&p[i][j]);
for(int S=(1<<n)-2,t=0;S;--S,t=0){
for(int i=S;i;i^=i&-i)t++;
for(int i=0;i<n;++i)
if(!((1<<i)&S))
for(int j=0;j<n;++j)
if((1<<j)&S)dp[S]+=dp[S^(1<<i)]*p[j][i];
dp[S]/=(double)(t*(t+1)>>1);
}
for(int i=0;i<n;i++)printf("%.6lf ",dp[1<<i]);
return 0;
}
```
# 树形DP
## 算法思想
## HDU2196 Computer
### 题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=2196
### 题目大意
计算树上所有点到距离他最远的点的距离。
### 思路
这个题目和求树的直径有点相似，都是进行了两遍dfs。
首先，本题是无根树，为了方便直接令1为根节点，转化为有根树进行DP。
那么，和一个点距离最远的点要么在其子树上，要么不在子树上，因此答案便是两种情况最大距离的较大值，也就是max(子树中与此点的最大距离,其父亲到其他子树距离的最大值+到父亲的距离)。
那么令$dp[0][i]$表示以$i$为根的子树中的点到根节点距离的最大值。
因为考虑到需要知道父亲到其他子树距离的最大值，如果当前点没有为其父亲贡献最大值，那么其父亲节点的$dp[0][fa[i]]$就是这个值，否则应该是父亲节点到其他子树的最大值，也就是父亲节点到所有子树距离的次大值，因此次大值也要记录，记为$dp[1][i]$。
$dp[0][i]$和$dp[1][i]$珂以通过一次dfs求出。
此时令$dp[2][i]$表示经过其父亲的最远距离，那么按照上面的思路珂以写出DP方程为：
$$
dp[2][i]=
\begin{cases}
max(dp[1][fa[i]]+dist_{i,fa[i]},dp[2][fa[i]]+dist_{i,fa[i]}),&dp[0][i]+dist_{i,fa[i]}==dp[0][fa[i]]\\
max(dp[0][fa[i]]+dist_{i,fa[i]},dp[2][fa[i]]+dist_{i,fa[i]}),&dp[0][i]+dist_{i,fa[i]}\ne dp[0][fa[i]]
\end{cases}
$$
最后，对于每个点，取$dp[2][i]$和$dp[0][i]$的较大值就是答案。
### code
```cpp
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 10007;
int n,dp[3][maxn],head[maxn],top;
struct node{int v,to,next;}edge[maxn<<1];
inline void addedge(int fr,int to,int val)
{
edge[++top].to=to;
edge[top].next=head[fr];
edge[top].v=val;
head[fr]=top;
return;
}
void dfs(int o,int fa)
{
for(int i=head[o],v=edge[i].to;i;i=edge[i].next,v=edge[i].to)
{
if(v==fa)continue;
dfs(v,o);
if(dp[0][o]<dp[0][v]+edge[i].v)dp[1][o]=dp[0][o],dp[0][o]=dp[0][v]+edge[i].v;
else if(dp[1][o]<dp[0][v]+edge[i].v)dp[1][o]=dp[0][v]+edge[i].v;
}
}
void search(int o,int fa,int val)
{
if(dp[0][o]+val==dp[0][fa])dp[2][o]=max(dp[1][fa]+val,dp[2][fa]+val);
else dp[2][o]=max(dp[0][fa]+val,dp[2][fa]+val);
for(int i=head[o],v=edge[i].to;i;i=edge[i].next,v=edge[i].to)if(v!=fa)search(v,o,edge[i].v);
}
int main()
{
while(~scanf("%d",&n))
{
memset(dp,0,sizeof(dp)),top=0,memset(head,0,sizeof(head));
for(register int i=2,x,y;i<=n;i++)scanf("%d%d",&x,&y),addedge(i,x,y),addedge(x,i,y);
dfs(1,1),search(1,1,0);
for(register int i=1;i<=n;i++)printf("%d\n",max(dp[2][i],dp[0][i]));
}
return 0;
}
```
# 背包DP
## 二维背包:[二维费用的背包问题](https://www.acwing.com/problem/content/description/8/)
$dp[i][j][k]=max\{dp[i-1][j-v[i]][k-m[i]]\}+w[i],j\in[v[i],V],k\in[m[i],M]$
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1005;
int n,V,M,v[maxn],m[maxn],w[maxn],dp[maxn][maxn];
int main()
{
scanf("%d%d%d",&n,&V,&M);
for(register int i=1;i<=n;++i)scanf("%d%d%d",&v[i],&m[i],&w[i]);
for(register int i=1;i<=n;++i)
for(register int j=V;j>=v[i];j--)
for(register int k=m[i];k<=M;k++)
dp[j][k]=max(dp[j-v[i]][k-m[i]]+w[i],dp[j][k]);
printf("%d",dp[V][M]);
return 0;
}
```
## 单调队列优化多重背包
### 算法思想
多重背包DP转移方程为：
$$
dp[i][j]=max\{dp[i-1][j-k\times c[i]]+k\times w[i]\},k\in[1,min\{num[i],\frac{j}{c[i]}\}]
$$
### 例：[P1782 旅行商的背包](https://www.luogu.com.cn/problem/P1782 )
``` cpp
```
## CF730J Bottles
### 题目链接
https://www.luogu.com.cn/problem/CF730J
### 题目大意
有一些瓶子，每个瓶子里都有水，已知瓶子的体积和瓶中水的体积，现在想把所有水都倒入尽可能少的瓶子中，求最少的瓶子个数和在瓶子个数最小的情况下，需要移动的水的体积最小值。
### 思路
~~洛谷诚欺我！这个难度就省选/NOI-了？~~
首先考虑最少的瓶子数，这个珂以用瓶子的体积直接跑一遍01背包，令$dp[i]$表示得到体积$i$的最小瓶子数，然后找到$i\ge$水的总体积的最小dp[i]即可。
体积最小值，就需要在$dp$记录的状态中增加一条信息，就是所选择的瓶子中水的体积，只要用水的总体积减去这个就是需要移动的水的体积了。为了最小化需要移动的水的体积，只需在保证瓶子数目最小的情况下，保留所选瓶子中最小的体积数即可。
这样，令$dp[i][0]$表示组合出容量为$i$的最小瓶子数，$dp[i][1]$表示在瓶子数最小的情况下瓶中水的体积和的最小值，那么得到DP转移方程为：($a[i]$为瓶子的容积，$b[i]$为瓶子中水的体积)
$$
dp[i]=
\begin{cases}
dp[i-a[j]][0]+1,dp[i-a[j]][1]+b[j],&dp[i-a[j]][0]+1>dp[i][0]\\
dp[i][0],dp[i-a[j]][1]+b[j],&dp[i-a[j]][0]+1=dp[i][0]\&dp[i][1]<dp[i-a[j]][1]+b[j]
\end{cases}
$$
### code
``` cpp
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 105;
int n,a[maxn],b[maxn],dp[maxn*maxn][2],t,nowans=maxn,nowt,now;
int main()
{
scanf("%d",&n),memset(dp,0x3f,sizeof(dp)),dp[0][0]=dp[0][1]=0;
for(register int i=1;i<=n;i++)scanf("%d",&b[i]),b[0]+=b[i],t+=b[i];
for(register int i=1;i<=n;i++)scanf("%d",&a[i]);now=a[1];
for(register int i=1;i<=n;now+=a[++i])
for(register int j=now;j>=a[i];j--)
if(dp[j][0]>dp[j-a[i]][0]+1)dp[j][0]=dp[j-a[i]][0]+1,dp[j][1]=dp[j-a[i]][1]+b[i];
else if(dp[j][0]==dp[j-a[i]][0]+1&&dp[j][1]<dp[j-a[i]][1]+b[i])dp[j][1]=dp[j-a[i]][1]+b[i];
do{if(nowans>dp[t][0])nowans=dp[t][0],nowt=dp[t][1];else if(nowans==dp[t][0]&&nowt<dp[t][1])nowt=dp[t][1];}while(++t<=now);
printf("%d %d",nowans,b[0]-nowt);
return 0;
}
```