深入探讨：DP技术的消亡与未来趋势

一般的DP的步骤

1. 定义状态：找通解
   
   
   
   1. 关注题目需要的东西
   
   
   2. 状态确定，输出就确定
   
   
   3. 将状态的准确描述记录下来
   
   
   
   


2. 寻找状态转移方程：描述一个子问题如何用更小的子问题得到


3. 确定边界条件：最小的子问题或不满足状态转移方程的状态

一些小小的DP

例1. 摆花

先看一眼题面，容易设计状态。

设 dp[i][j] 表示前 \(i\) 种花一共摆了 \(j\) 盆时的种类数。

然后让每一位加上前面可以达到的位的答案。

答案即为 dp[n][m] 。

代码实现：

int main()
{
scanf("%d%d",&n,&m);
for(register int i=1;i<=n;i++)
scanf("%d",&a[i]);
dp[0][0]=1;
for(register int i=1;i<=n;i++)
for(register int j=0;j<=m;j++)
for(register int k=0;k<=a[i];k++)
if(j>=k)dp[i][j]=(dp[i][j]+dp[i-1][j-k])%MOD;//需要保证摆的花不超过j盆且不超过限制a[i]
printf("%d",dp[n][m]);
return 0;
}


例2. 木棍加工

一眼可以看出是求下降子序列的个数。

根据某个著名的定理，下降子序列的个数等于最长上升子序列的长度。

根据一维排序再求最长上升子序列长度即可。

代码实现：

struct node
{
int l,r;
}e[MAXN];
int n;
inline bool cmp(node x,node y)
{
if(x.l==y.l)return x.r>y.r;
return x.l>y.l;
}
int dp[MAXN];
int main()
{
scanf("%d",&n);
for(register int i=1;i<=n;i++)
scanf("%d%d",&e[i].l,&e[i].r);
sort(e+1,e+1+n,cmp);
for(register int i=1;i<=n;i++)
{
for(register int j=1;j if(e[j].r }
int maxn=-0x7f7f7f7f;
for(register int i=1;i<=n;i++)
maxn=max(maxn,dp[i]);
printf("%d",maxn+1);
return 0;
}


例3. 书本整理

不整齐度和剩下的书有关，所以状态和剩下的书有关。

设 dp[i][j] 表示前 \(i\) 本书中留下了 \(j\) 本且第 \(i\) 本一定选的最小不整齐度。

寻找每一个可以与当前遍历到的 \(i\) 匹配的 \(p\) 即可。

代码实现：

int main()
{
scanf("%d%d",&n,&k);
for(register int i=1;i<=n;i++)
scanf("%d%d",&e[i].l,&e[i].r);
sort(e+1,e+1+n,cmp);
for(register int i=1;i<=n;i++)
for(register int j=1;j<=n-k;j++)
dp[i][j]=0x7f7f7f7f;
for(register int i=1;i<=n;i++)
dp[i][0]=dp[i][1]=0;
for(register int i=1;i<=n;i++)
for(register int j=1;j<=min(i,n-k);j++)
for(register int p=j-1;p<=i-1;p++)
dp[i][j]=min(dp[i][j],dp[p][j-1]+abs(e[i].r-e[p].r));
int minn=0x7f7f7f7f;
for(register int i=n-k;i<=n;i++)
minn=min(minn,dp[i][n-k]);
printf("%d",minn);
return 0;
}


例4. Modulo Sum

直接搞DP是 \(O(nm)\) 的，肯定会炸。

考虑一个小优化：当 \(n\ge m\) 时必定有解。

我们假设 \(dp_{i,j}\) 表示考虑在前 \(i\) 个数中选数，是否可能使得它们的和除以 \(m\) 的余数为 \(j\) ，初始状态 \(dp_{i,a_{i}}=1\)，枚举每个数和余数进行转移即可。

代码实现：

#include
using namespace std;
const int MAXN=1e3+5;
int n,m;
bool dp[MAXN][MAXN];
int a[MAXN];
int main()
{
scanf("%d%d",&n,&m);
if(n>m)
{
puts("YES");
return 0;
}
for(register int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
a[i]%=m;
dp[i][a[i]]=1;
if(!a[i])
{
puts("YES");
return 0;
}
}
for(register int i=1;i<=n;i++)
{
for(register int j=0;j {
dp[i][j]|=dp[i-1][j];
dp[i][(j+a[i])%m]|=dp[i-1][j];
}
if(dp[i][0])
{
puts("YES");
return 0;
}
}
puts("NO");
return 0;
}


现在有一点图的变化。

例1. 挖地雷

有很多方法，比如暴搜。

可能第一印象是拓扑+DP

手玩可以发现，一定是从编号小的地窖跑到编号较大的地窖。

所以二维循环即可。

代码实现：

区间DP

一般是求一个区间内的最大值，最小值，方案数。

判别：

• 从不同位置开始递推得到的结果可能不一样。

  
  



• 合并类或拆分类。

  
  

区间DP一般有三个循环：

• 第一个循环一般是枚举阶段（子问题）

  
  



• 第二个循环枚举所有的状态（情形）

  
  



• 第三个循环枚举决策点（从哪里转移）

  
  

例1. 石子合并(加强版)

区间DP/GarsiaWachs算法板子题

GarsiaWachs算法是专门解决石子合并问题，好像是线性复杂度。

算法流程大致如下：

1. 寻找最小的满足 \(a_{k-1}\leqslant a_{k+1}\) 的 \(k\) ，将 \(a_{k}\) 与 \(a_{k-1}\) 合并。

   
   



2. 从 \(k\) 向前寻找第一个满足 \(a_j\gt a_k+a_{k-1}\) 的 \(j\) ，将 \(a_k+a_{k-1}\) 插入在 \(a_j\) 后面。

   
   



3. 当只剩下一个数时，那个数就是答案。

   
   

区间DP：

#include
using namespace std;
const int MAXN=305;
int n,val[MAXN],sum[MAXN];
int dp[MAXN][MAXN];
int main()
{
scanf("%d",&n);
memset(dp,0x7f,sizeof dp);
for(register int i=1;i<=n;i++)
{
scanf("%d",&val[i]);
sum[i]=sum[i-1]+val[i];
dp[i][i]=0;
}
for(register int len=2;len<=n;len++)
for(register int i=1;i+len-1<=n;i++)
{
int j=i+len-1;
for(register int k=i;k dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
}
printf("%d",dp[1][n]);
return 0;
}


GarsiaWachs：

#include
#define int long long
using namespace std;
int ans,n;
vectorv;
inline int merge()
{
int k=v.size()-2;
for(register int i=0;i if(v[i]<=v[i+2])
{
k=i;
break;
}
int now=v[k]+v[k+1];
v.erase(v.begin()+k);
v.erase(v.begin()+k);
int wh=-1;
for(register int i=k-1;i>=0;i--)
if(v[i]>now)
{
wh=i;
break;
}
v.insert(v.begin()+wh+1,now);
return now;
}
signed main()
{
scanf("%lld",&n);
for(register int i=1;i<=n;i++)
{
int op;
scanf("%lld",&op);
v.push_back(op);
}
for(register int i=1;i ans+=merge();
printf("%lld",ans);
return 0;
}


例2. 248 G

还是区间DP板子。

只要两边相等，就可以将两边合并。

代码实现：

#include
using namespace std;
const int MAXN=305;
int n,val[MAXN];
int dp[MAXN][MAXN];
int main()
{
scanf("%d",&n);
memset(dp,-0x7f,sizeof dp);
for(register int i=1;i<=n;i++)
{
scanf("%d",&val[i]);
dp[i][i]=val[i];
}
for(register int len=2;len<=n;len++)
for(register int i=1;i+len-1<=n;i++)
{
int j=i+len-1;
for(register int k=i;k if(dp[i][k]==dp[k+1][j])dp[i][j]=max(dp[i][j],dp[i][k]+1);
}
int maxn=0;
for(register int i=1;i<=n;i++)
for(register int j=i;j<=n;j++)
maxn=max(maxn,dp[i][j]);
printf("%d",maxn);
return 0;
}


例3. Cheapest Palindrome G

对于一个区间，强制它要是一个回文串。

所以对于每一个区间 \([i,j]\) ，有以下转移：

\(dp_{i,j}=\min\begin{cases}dp_{i+1,j}+\min(ins_i,del_i)\\dp_{i,j-1}+\min(ins_j,del_j)\\\text{if }a_i=a_j~~~~~~~~~~dp_{i+1,j-1}\end{cases}\)

代码实现：

#include
using namespace std;
const int MAXN=2005;
int n,m;
string a;
int dp[MAXN][MAXN];
mapins,del;
signed main()
{
scanf("%d%d",&n,&m);
cin>>a;
a=' '+a;
memset(dp,0x7f,sizeof dp);
for(register int i=1;i<=n;i++)
{
char op;
int in,de;
cin>>op>>in>>de;
ins[op]=in;
del[op]=de;
}
for(register int i=1;i<=m;i++)
dp[i][i]=0;
for(register int len=2;len<=m;len++)
for(register int i=1;i+len-1<=m;i++)
{
int j=i+len-1;
if(a[i]==a[j])
{
if(len==2)dp[i][j]=0;
else dp[i][j]=min(dp[i][j],dp[i+1][j-1]);
}
dp[i][j]=min(dp[i][j],dp[i][j-1]+ins[a[j]]);
dp[i][j]=min(dp[i][j],dp[i][j-1]+del[a[j]]);
dp[i][j]=min(dp[i][j],dp[i+1][j]+ins[a[i]]);
dp[i][j]=min(dp[i][j],dp[i+1][j]+del[a[i]]);
}
printf("%d",dp[1][m]);
return 0;
}


例4. 合唱队

首先套路设 \(dp_{i,j}\) 为区间 \([i,j]\) 的方案数。

然后发现状态设计有问题。

所以再加一维表示最后一个是从哪边进来的。

有一个小坑点：只有一个人时从左边右边进来都一样，只要初始化一边即可。

代码实现：

#include
using namespace std;
const int MAXN=2005;
const int MOD=19650827;
int n;
int a[MAXN];
int dp[MAXN][MAXN][2];
int main()
{
scanf("%d",&n);
for(register int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(register int i=1;i<=n;i++)
dp[i][i][0]=1;
for(register int len=2;len<=n;len++)
for(register int i=1;i+len-1<=n;i++)
{
int j=i+len-1;
if(a[i]a[i])dp[i][j][1]=(dp[i][j][1]+dp[i][j-1][0])%MOD;
if(a[j]>a[j-1])dp[i][j][1]=(dp[i][j][1]+dp[i][j-1][1])%MOD;
}
printf("%d",(dp[1][n][0]+dp[1][n][1])%MOD);
return 0;
}


例5. 关路灯

有了上一题的经验，一上来就可以设 \(dp_{i,j,0/1}\) 表示在区间 \([i,j]\) 内最后一个是 \(i/j\) 的最小代价。

转移也十分套路，按照思路模拟即可。

需要注意的是初始化。

因为给定了初始位置为 \(c\) 。

所以 \(dp_{i,i}=|a_c-a_i|\times (sum_n-w_c)\)

代码实现:

#include
using namespace std;
const int MAXN=55;
int n,c;
int a[MAXN],w[MAXN];
int sum[MAXN];
int dp[MAXN][MAXN][2];
int main()
{
scanf("%d%d",&n,&c);
for(register int i=1;i<=n;i++)
{
scanf("%d%d",&a[i],&w[i]);
sum[i]=sum[i-1]+w[i];
}
for(register int i=1;i<=n;i++)
dp[i][i][0]=dp[i][i][1]=abs(a[i]-a[c])*(sum[n]-w[c]);
for(register int len=2;len<=n;len++)
for(register int i=1;i+len-1<=n;i++)
{
int j=i+len-1;
dp[i][j][0]=min(dp[i+1][j][0]+(a[i+1]-a[i])*(sum[n]+sum[i]-sum[j]),dp[i+1][j][1]+(a[j]-a[i])*(sum[n]+sum[i]-sum[j]));
dp[i][j][1]=min(dp[i][j-1][0]+(a[j]-a[i])*(sum[n]+sum[i-1]-sum[j-1]),dp[i][j-1][1]+(a[j]-a[j-1])*(sum[n]+sum[i-1]-sum[j-1]));
}
printf("%d",min(dp[1][n][0],dp[1][n][1]));
return 0;
}


换根DP

对于一类树形DP，若节点不确定，且答案会随着根节点的不同而变换，这种树形DP可以称之为换根DP。

例一. STA-Station

步骤1. 定义 \(dp_i\) 表示以 \(i\) 为根节点的子树的最大深度和，然后任意指定节点跑一遍树形DP。

步骤2. 定义 \(f_i\) 表示以 \(i\) 为全局根节点时的最大深度和，然后以 \(rt\) 再跑一遍树形DP。

步骤3. 在 \(f_1\) 到 \(f_n\) 中取最大值即为答案。

代码实现：

#include
#define int long long
using namespace std;
const int MAXN=2e6+5;
struct node
{
int to,nxt;
}e[MAXN];
int head[MAXN],cnt;
inline void add(int x,int y)
{
e[++cnt].to=y;
e[cnt].nxt=head[x];
head[x]=cnt;
}
int n;
int f[MAXN],dep[MAXN],siz[MAXN];
inline void dfs1(int x,int fa)
{
dep[x]=dep[fa]+1;
siz[x]=1;
for(register int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(y==fa)continue;
dfs1(y,x);
siz[x]+=siz[y];
}
}
inline void dfs2(int x,int fa)
{
for(register int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(y==fa)continue;
f[y]=f[x]-siz[y]+(n-siz[y]);
dfs2(y,x);
}
}
signed main()
{
scanf("%lld",&n);
for(register int i=1;i {
int x,y;
scanf("%lld%lld",&x,&y);
add(x,y);
add(y,x);
}
dfs1(1,0);
for(register int i=1;i<=n;i++)
f[1]+=dep[i];
dfs2(1,0);
int maxn=-0x7f7f7f7f,id;
for(register int i=1;i<=n;i++)
if(f[i]>maxn)
{
maxn=f[i];
id=i;
}
printf("%lld",id);
return 0;
}


例二. Great Cow Gathering G

差不多，也是板子。

代码实现：

#include
#define int long long
using namespace std;
const int MAXN=4e5+5;
struct node
{
int to,nxt,len;
}e[MAXN];
int head[MAXN],cnt;
inline void add(int x,int y,int z)
{
e[++cnt].to=y;
e[cnt].len=z;
e[cnt].nxt=head[x];
head[x]=cnt;
}
int n,sum;
int val[MAXN];
int dp[MAXN],f[MAXN],siz[MAXN];
inline void dfs1(int x,int fa)
{
siz[x]=val[x];
for(register int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to,z=e[i].len;
if(y==fa)continue;
dfs1(y,x,i);
siz[x]+=siz[y];
dp[x]=dp[x]+dp[y]+siz[y]*z;
}
}
inline void dfs2(int x,int fa)
{
for(register int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to,z=e[i].len;
if(y==fa)continue;
f[y]=f[x]-siz[y]*z+(sum-siz[y])*z;
dfs2(y,x);
}
}
signed main()
{
scanf("%lld",&n);
for(register int i=1;i<=n;i++)
{
scanf("%lld",&val[i]);
sum+=val[i];
}
for(register int i=1;i {
int x,y,z;
scanf("%lld%lld%lld",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
dfs1(1,0,0);
f[1]=dp[1];
// cout< dfs2(1,0);
int minn=0x7f7f7f7f7f7f;
for(register int i=1;i<=n;i++)
minn=min(minn,f[i]);
printf("%lld",minn);
return 0;
}


状压DP

定义：当状态的维度很多，而每一个维度的取值是bool值时，则可以用二进制数值去表示一个状态，这种DP被称为状压DP

基本的位运算：

按位与（ \(\&\) ）：两个整数在二进制下逐位比较，同一位有 \(2\) 个 \(1\) ，则结果为 \(1\) ，否则为 \(0\) 。

按位或（ \(|\) ）：两个整数在二进制下逐位比较，同一位有 \(1\) ，则结果为 \(1\) ，否则为 \(0\) 。

按位异或（ \(^\) ）： 两个整数在二进制下逐位比较，同一位不同则为 \(1\) ，否则为 \(0\) 。

按位取反（ ~ ）：字面意思。

常见位操作意义：