DP总结

线性DP

• 定义:

  具有线性"阶段"划分的$DP$被称为线性$DP$。

• 经典模型

  $LIS$ , $LCS$ , $LCIS$(最长公共上升子序列) , $最长公共子序列$ , $数字三角形$。

• 例题：

  1. LCS

     题意：

     求两个字符串中字典序最小的$LCS$。

     方法:

     用 $vector$ 记录下每一个状态下的答案。

  2. 最长上升子序列(LIS)

     题意：

     • 给定一个长为 n 的序列 $a_i$，求这个序列的最长单调上升子序列长度。
     • 要求 $O(n log_n)$ 。

     方法：

     在长度一定的情况下，若结尾元素更小，那么最终答案也就更优。

     所以我们维护一个数组表示当前的$LIS$，每一次插入当前元素。

     code :

     #include<bits/stdc++.h>
     #define int long long
     #define rep(i,a,b) for(int i=(a);i<=(b);++i)
     using namespace std;
     
     const int N=1e6 +3;
     int n,m,a[N],f[N];
     
     signed main()
     {
     	cin>>n; for(int i=1;i<=n;i++) cin>>a[i];
     	memset(f,0x3f,sizeof f);
     	for(int i=1;i<=n;i++) *upper_bound(f+1,f+n+1,a[i])=a[i];
     	int res=1; while(f[res]!=f[0]) res++;
     	cout<<res-1<<endl;
     	return 0;
     }

二维平面上的*P与 状态压缩DP

• 怎样判断？

  二维平面看题面。

  状态压缩的$n\le 22$。

• 例题：

  1. Grid 2

     题目：

     给一个 H×W 的网格，每一步只能向右或向下走，给出 $n$ 个坐标，这些坐标对应的位置不能经过，求从左上角 (1,1)走到右下角 (H,W) 的方案数，答案对 $10^9+7$ 取模。

     思路：

     首先对于 $f_{i,j}\ (1\le i\le H,1\le j\le W)$ 可行性显然，但空间不够。我们只能对着 $n$ 个坐标开数组。

     我们设方程 $f_i$ 表示从 (1,1) 做到第i个坐标，且只经过第$i$个坐标的方案总数。

     那么，我们尝试使用容斥原理进行转移

     • 从 (1,1) 到 ($x_i,y_i$) 的方案数是 ${C_{x_i-1+y_i-1}^{x_i -1}}$
     • 从某一个坐标转移过来的方案数是 $\sum C_{x_i-x_j+y_i-y_j}^{x_i -x_j} $

  2. Matching

     题目：

     给定 N，表示有 N 个男生和 N 个女生，再给你一个矩阵 a，如果$a_{i,j}$ 等于 1，表示 i 这个男生和 j 这个女生可以匹配成一对，否则不能。 问要匹配 N 对的方案数。答案对 $10^9+7$ 取模。

     思路：

     状压男生，枚举女生

区间DP

​ 都离不开三重循环: $\sum\limits_{长度} \sum\limits_{左端点} \sum\limits_{转移的断点} f...$

1. 石子合并

   题目：

   在一个圆形操场的四周摆放 N 堆石子，现要将石子有次序地合并成一堆，规定每次只能选相邻的 2 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。

   试设计出一个算法,计算出将 N* 堆石子合并成 1 堆的最小得分和最大得分。

   思路：

   令dp[i][j]表示区间[i,j]的最小价值。

   不妨从终点考虑问题，即结果为两个子区间合并的最小值再加上合并需要的代价即可。

   枚举两个子区间，即枚举这个区间的中间点k，使这个区间被分为[i,k]和[k+1,j]两个区间，取一遍最小值加上合并的即为当前区间所求。

   至于合并的代价，用前缀和即可。

   所以dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1])

2. Deque

   题目：

   给定 N 个数的序列 $A$。

   A 和 B 轮流取数，每个人每次可以从序列头部或者尾部取走一个数（直到序列为空）。

   A 和 B 都希望自己取得的数的总和尽可能大。

   假设最优策略下，A 取得的数的总和是 X，B 取得的数的总和是 Y， 请输出 X-Y。

   思路：

   显然游戏过程中剩下的数必然是连续的一段。设 $f_{i,j}$ 表示剩下下标为 $[i,j]$ 的数时，先手（并非当前的先手而是开始时的先手，下同）能取得的最大分数差。

   分两种情况讨论：

   • 已经取走的数为偶数个，此时先手取，$f_{i,j}$=$max⁡$ ($f_{i+1,j}+a_i$,$f_{i,j-1}$,$f_{i,j-1}+a_j$)
   • 已经取走的数为奇数个，此时后手取，$f_{i,j}$=$max$⁡ ($f_{i+1,j}-a_i$,$f_{i,j-1}$,$f_{i,j-1}-a_j$)

换根DP

​ 本质上只是把序列变成了树

1. Subtree

   题目：

   有一个 n 个节点的树，对一些节点染色，使得所有被染色的节点是一个连通块。求对于 $1,2,3,...,n$每个节点，该节点被染色的方案个数。所有答案对 M 取模。

   思路：

   我们设$p_i$表示以$i$为跟的子树中的可行方案数,$q_i$表示$i$的父节点中除了$i$的方案数。

   那么，有$ans_i=(q_i+1)*p_i$。

DP优化

​ 根据方程运用相应的数据结构即可。