本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-04 10:37:13
DP
前置
最难点在于看出来是dp
(易与网络流混淆)
状态，转移，初始化
状态最基础(关键)
转移：状态之间的关系（简单）
初始化：状态的边界条件
设计状态：找到题目中所有在变化的量，将其作为状态（先塞再删）
不能用状态以外的信息
eg：数字三角形上，求走到最后%100最大为多少
不同于数字三角形原题，目前最优不保证一直最优
（所有dp的错误都来自状态不够）
所以再加一维状态
$f_{i,j,k}$ 表示在 $( i , j )$ 位置上,模数为 $k$ 是否可能
转移方式
用别人求自己
用自己求别人
（博弈论dp）记忆化搜索（不好for的时候）
分类
有模版：背包，区间，树形，数位，状压，插头（不考），排列，博弈论
一般dp(更难)
eg:Paint Pearls
$n^2$ dp $f_i=f_j+[j+1,i]$中不同颜色的种数
$n\sqrt{n}$ dp(相同颜色的区间越长越好，最大代价为n,则最多$\sqrt{n}$种不同颜色，双指针处理区间)
排列dp
$n!$ 种排列中，满足要求的有多少
转移方法
把所有数从小到大或从大到小插入的过程
$f_i$ 表示 $i$ 已经被插入
枚举插入的位置，计算方案
eg $[1,n]$ 所有的排列中，逆序对数为偶数的数量
$f_{i,j}$表示，$[1,i]$已经被插入，当前j个逆序对的方案数
第i+1个数，插入k位置，会与其后的所有数形成逆序对
$f_{1,0}=1$
cin>>n;
f[1][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=i*(i-1)\/2;j++)\/\/逆序对数最多为每个数都 与后面的数 形成逆序对的情况
{
for(int k=0;k<=i;k++)
{
f[i+1][j+i-k]+=f[i][j];
}
}
}
针对本题优化： j:0/1
cin>>n;
f[1][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=1;j++)
{
for(int k=0;k<=i;k++)
{
f[i+1][(j+i-k)&1]+=f[i][j];
}
}
}
可优化到O(n)
O(1)
$n!/2$ (数学结论)
$f_{i,j}$ 表示 $[i,n]$插入，激动值为j的方案数
插入到前面，激动值+1； 插入到后面，激动值不变
背包
01背包
$f_{i,j}$ 前 $i$ 个物品考虑完毕，用了 $j$ 的体积的最大价值
$f_{i,j}=max(f_{i-1,j},f_{i-1,j-v_i}+w_i)$
完全背包
状态一样，枚举个数
优化
由于不关心到底选了多少个
所以$f_{i,j}$ 不从 $f_{i-1,j-v_i}$ 转移，从 $f_{i,j-v_i}$ 转移
将斜线拆为一竖一横
for(int i=1;i<=n;i--)
{
for(int j=0;j<m;j++)
{
f[i][j]=f[i-1][j];
if(j>=v[i])
{
f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
}
}
}
多重背包
每个物品有限个
（想办法将未知变为已知）
（可能的出新题方法：TA+TB=TC）
将物品个数进行二进制拆分
eg: 17=1+2+4+8+2
转化为01背包
复杂度：$O(nm\log_2{n})$
for(int i=1;i<=cnt;i++)
{
int tiji,jiazhi,geshu;
cin>>tiji>>jiazhi>>geshu;
int k=1;
while(k<=geshu)
{
n++;
v[n]=tiji*k;
w[n]=jiazhi*k;
geshu-=k;
k*=2;
}
if(geshu!=0)
{
n++;
v[n]=tiji*geshu;
w[n]=jiazhi*geshu;
}
}
正着跑一遍，倒着跑一遍，每次不算这个物品的区间，将两个区间拼起来
数位dp
eg给出l,r，求出$[l,r]$有几个数(不能 $r-l+1$ )
$[l,r]=[0,r]-[0,l-1]$
转移方法
从高位开始，一位一位填数,枚举下一位填什么
状态
$f_{i,j(0/1)}$ 表示已经填了i位，是否等于限制的方案数
int calc(int z)\/\/计算0~z所有数的数位之和
{
if(z==0)
{
return 1;
}
int n=0;
while(z)
{
n++;
x[n]=z%10;
z\/=10;
}
memset(f,0,sizeof(f));\/\/转化为前缀和，因此要清空
f[n+1][1]=1;\/\/只有一种方法，填 0
for(int i=n;i>=1;i--)\/\/当前要填y[i]的值，此时已经填了y[i+1~n]
{
for(int j=0;j<=1;j++)\/\/填y[i]之前，是<还是=
{
int up=9;\/\/能填的最大值
if(j==1)
{
up=x[i];
}
for(int k=0;k<=up;k++)
{
f[i][(j==1)&&(k==up)]+=f[i+1][j];
}
}
}
return f[1][0]+f[1][1];
}
eg 计算 $[l,r]$ 的数位和
int calc(int z)\/\/计算0~z所有数的数位之和
{
if(z==0)
{
return 1;
}
int n=0;
while(z)
{
n++;
x[n]=z%10;
z\/=10;
}
memset(f,0,sizeof(f));\/\/转化为前缀和，因此要清空
f[n+1][1]=1;\/\/只有一种方法，填 0
for(int i=n;i>=1;i--)\/\/当前要填y[i]的值，此时已经填了y[i+1~n]
{
for(int j=0;j<=1;j++)\/\/填y[i]之前，是<还是=
{
int up=9;\/\/能填的最大值
if(j==1)
{
up=x[i];
}
for(int k=0;k<=up;k++)
{
f[i][(j==1)&&(k==up)]+=f[i+1][j];
w[i][(j==1)&&(k==up)]+=f[i+1]*k+w[i+1][j];
}
}
}
return w[1][0]+w[1][1];
}
#include<bits\/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int a,b;
int f[15][2][15];
int x[15];
int calc(int z)
{
if(z==0)
{
return 0;
}
int n=0;
memset(x,0,sizeof(x));
while(z)
{
n++;
x[n]=z%10;
z\/=10;
}
memset(f,0,sizeof(f));
for(int i=1;i<=x[n];i++)
{
f[n][(i==x[n])][i]++;
}
for(int i=n-1;i>=1;i--)\/\/填好所有最高位的可能情况，防止前导0；
{
for(int j=1;j<=9;j++)
{
f[i][0][j]++;
}
}
for(int i=n;i>=1;i--)
{
for(int j=0;j<=1;j++)
{
for(int k=0;k<=9;k++)
{
int up=9;
if(j)
{
up=x[i];
}
for(int l=0;l<=up;l++)
{
if(abs(k-l)>=2)
{
f[i][(j==1)&&(l==up)][l]+=f[i+1][j][k];
}
}
}
}
}
int res=0;
for(int j=0;j<=1;j++)
{
for(int k=0;k<=9;k++)
{
res+=f[1][j][k];
}
}
return res;
}
signed main()
{
cin>>a>>b;
int ans=calc(b)-calc(a-1);
cout<<ans;
return 0;
}
$f_{i,j,k}$ 分别表示位数，是否有当前位限制，积为k的方案数
显然要炸
由于$ 10 $以内的数质因数分解只有2,3,5,7
$f_{i,0/1,a,b,c,d}$分别表示位数，是否有限制，积为 $2^a\times3^b\times5^c\times7^d$ 的方案数
但是还是过不了
但是 $a,b,c,d$ 不能同时取最大，肯定有大量不合法的
将合法的 $2^a\times3^b\times5^c\times7^d$ 存在z数组中（大约3万个）
将4维压回一维
这样就能过了
区间dp
特征（第一类区间dp，不绝对）
合并，相邻
方法
枚举分界点
（注意，按区间大小从小到大转移，先长度，再区间，否则就爆了）
第二类
eg 给定字符串，求回文子序列的数量(HDU4632)
$f_{l,r}=f_{l+1,r}+f_{l,r-1}-f_{l+1,r-1}$
$if( s_l == s_r ) f_{l,r}+=f_{l+1,r-1}$
方法
扔掉左端点和右端点
关键词（不绝对）
子序列
树形dp
在树上做的dp
eg 给定n个点的树，求这棵树有多少点
$f_i$ 表示以 $i$ 为根的子树内，有多少点
转移
把所有儿子的信息整合
eg 给定一棵n个点的树，每边有长度，$dist(i,j)$ 表示i到j的路径长度，求$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}dist(i,j)$
暴力求肯定炸
我们只关心一条边经过了几次
$(i,j)$ 肯定一个在子树内，一个在子树外
将内外的点数相乘，全部加起来
答案再乘2； （$i,j$ 都是1~n循环，$(i,j)$ 一次，$(j,i)$ 一次）
eg
求$max dist(i,j)$
求最长路，次长路即可
vector<Node> G[N];
int f[N];\/\/最长
int g[N];\/\/次长距离
void dfs(int u,int fa)
{
f[u]=0;
g[u]=0;
for(auto x:G[u])
{
v=x.v;
w=x.w;
if(v==fa)
{
continue;
}
dfs(v,u);
int dis=f[v]+w;
if(dis>f[u])
{
g[u]=f[u];
f[u]=dis;
}
else if(dis>g[u])
{
g[u]=dis;
}
}
}
eg 求最大独立集
最大独立集：选出尽量多的点，使得点与点之间不相邻
#include <bits\/stdc++.h>
#define endl '\n'
using namespace std;
const int N=6e3+5;
short r[N];
int f[N][2];
int n;
vector<int> g[N];
int ind[N];
int s;
void dfs(int u,int fa)
{
f[u][1]=r[u];
f[u][0]=0;
for(auto v:g[u])
{
if(v==fa)
{
continue;
}
dfs(v,u);
f[u][0]+=max(f[v][0],f[v][1]);
\/\/u不来,v可来可不来
f[u][1]+=f[v][0];
\/\/u来,v一定不来
}
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>r[i];
}
for(int i=1;i<n;i++)
{
int x,y;
cin>>x>>y;
g[y].push_back(x);
ind[x]++;
}
for(int i=1;i<=n;i++)
{
if(ind[i]==0)
{
s=i;
break;
}
}
dfs(s,0);
cout<<max(f[s][1],f[s][0]);
return 0;
}
#include <bits\/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1510;
const int INF=0x3f3f3f3f;
int n;
int r[N];
int m;
int f[N][3];
\/\/f[i][0] 表示 该节点不选 孩子看
\/\/f[i][1] 表示 该节点选
\/\/f[i][2] 表示 该节点不选 父亲看
vector<int > g[N];
void dfs(int u, int fa)
{
f[u][1]=r[u];
bool flag=0;
int tmp = INF;
for(auto v : g[u])
{
if(v == fa)
{
continue;
}
dfs(v, u);
f[u][1] += min({f[v][0], f[v][1], f[v][2]});
f[u][2] += min(f[v][0], f[v][1]);
if(f[v][1] <= f[v][0])
{
flag=1;
}
else
{
tmp = min(tmp, f[v][1] - f[v][0]);
}
f[u][0] += min(f[v][0], f[v][1]);
}
if(flag == false)
{
f[u][0] += tmp;
}
\/\/f[u][0]也可通过辅助数组记录前i个儿子中是否有保安的情况最小花费
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
cin>>r[x];
cin>>m;
for(int j=1;j<=m;j++)
{
int y;
cin>>y;
g[x].push_back(y);
g[y].push_back(x);
}
}
dfs(1,0);
cout<<min(f[1][0],f[1][1]);
return 0;
}
状压dp
eg 旅行商问题
#include<bits\/stdc++.h>
using namespace std;
const int N=1e5+10;
const int inf=0x3f3f3f3f;
int n;
double f[1<<20][20];\/\/f[s][i] 当前在i点 s代表那些点被走过
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>x[i]>>y[i];
}
for(int i=0;i<(1<<n);i++)
{
for(int j=0;j<n;j++)
{
f[i][j]=1e20;
}
}
f[1][0]=0;
for(int i=0;i<(1<<n);i++)
{
for(int j=0;j<n;j++)
{
if(i&(1<<j))
{
for(int k=0;k<n;k++)
{
if((1&(1<<k))==0)
{
f[i|(1<<k)][k]=min(f[i|(1<<k)][k],f[i][j]+dis(j,k));
}
}
}
}
}
double ans=1e20;
for(int i=0;i<n;i++)
{
ans=min(ans,f[(1<<n)-1][i]);
}
cout<<ans;
return 0;
}
特征
n不大
$f_{i,j}$ 表示前i行，第 $i$ 行状态为j的方案数
eg互不侵犯
改状态，加一维表示国王数量
一般dp
优化
eg 从一号点出发,走 $k$ 步到 $n$ 点的方案数
$m[i][j]=1$ 表示 $i,j$ 之间有路
$ f_{i,j}=\sum\limits_{k=1}^{n} f_{i-1,k}\times m_{k,j}$
$f_{i,1,j}=\sum\limits_{k=1}^{n} f_{i-1,1,k}\times m_{k,j}$
$f_i[1][j]=\sum\limits_{k=1}^{n} f_{i-1}[1][k]\times m[k][j]$
$ f_t=f_{t-1}\times m$
$f_t=f_0\times m^{t}$
矩阵快速幂
特征
1.$f_{i}$ 只和 $f_{i-1}$ 有关
转移系数 $ m $ 与 $ i $ 无关
$ t $很大
eg
拆边,将其拆为边权为$1$
但是本题为有向图，还有自环，最多拆成共有$n+8n^2$ 个点
$800$ 多个点，$n^3$接个$\log_2 t$ 很愉快地炸了
但是有一些点可以重复利用
可以每个点连一条链，每当有原来的点相连，就向外拐出
最多$90$ 个点
这样就转化为上一题了
eg 题意同$T1$ 每个点 $r$ 个入度 $ r $ 个出度
$in_{i,j}$ 表示$i$ 点的第$j$个出度
$out_{i,j}$ 同理
$m_{i,j}$ : 从$ i$到$j$ 有几条边
$m_{i,j}=\sum\limits {k=1}^{r} out{i,k}\times in_{j,k}$
($n<=10^3,r<=20,t<=10^9$)
从$r$入手
观察$m$ ,发现如果将$in$的两维存反，$m=in\times out$
$m^t=(out\times in)^t = out\times (in\times out)^{t-1}\times in$
$m$ 是$n\times n$ 的矩阵
$in$ 是 $r\times n$ 的矩阵(存反后)
$out$ 是 $n\times r$ 的矩阵
所以$in\times out$ 是$r\times r$的矩阵
将$n^3\times log_2{t}$ 复杂度转化为 $r^3\times log_2{t}$
博弈论dp
eg $A,B$两人,有数$n$，两人有$4$种操作,将$n$ 减1,2,4,8
$f[i]$ 表示先手必输还是必赢
$f[-7]$到 $f[0]$ 为true
所有能转移到的状态如果有false，那么自己必胜
如果全为true 那么自己必败
bool f[N];\/\/f[i]表示数为i时必胜还是必败
bool g[N];\/\/g[i]代表f[i]求没求过
int a[]={1,2,4,8};
bool dfs(int i)
{
if(i<=0)
{
return true;
}
if(g[i])
{
return f[i];
}
g[i]=1;
f[i]=0;
for(int j=0;j<4;j++)
{
if(!dfs(i-a[j]))
{
f[i]=1;
}
}
return f[i];
}
总结（第一类）
状态为游戏状态
如果能转移到必败态，那么必胜
如果不能，那么必败
eg
有$a$ 数组，不能把$a_i$ 变的$<=0$,谁无法操作，即为输
（每次$-1,-2,-4,-8$）
定义$sg$值
- 必败态的$sg$值为$0$
- $sg[i]=mex(sg_[i-1],sg_[i-2],sg_[i-4],sg_[i-8])$( $mex$ 表示最小没有出现过的自然数)
sg定理
$sg[a_1][a_2][a_3].......[a_n]= sg[a_1] \oplus sg[a_2] \oplus sg[a_3]......^sg[a_n]$
特征（第二类）
多个游戏
做法
sg值dp
转化为Nim石子游戏问题
经典例题 Nim石子游戏问题
$n$堆石子，二人轮流取石子，至少取一个，谁先取完就输
$sg[0]=0;$
$sg[1]=1;$
$sg[2]=2$
$...$
将$n$ 堆石子数异或起来
番外
“我们今天不讲（插头dp），又不考，（插头dp）如果出了就尽情骂出题人就行了，不用克制，不用收敛”
英文题面读不懂怎么办？ fanyi.baidu.com
比今年，啊不，去年noipT4简单，今年题是啥我还不知道，我也不知道我还出不出题，我已经有几年没出题了
"同学们私聊我问问题的时候注意一下是不是开了陌生人不能发消息"
"种国王"
"时间和空间都比较炸裂"
鲁ICP备2025150228号