一、算法优势轮廓线 DP 是面向网格、棋盘模型的状压 DP 进阶算法能够解决普通逐行状压 DP 无法覆盖的网格计数问题算法效率远高于朴素 DFS。该算法采用逐格转移的方式计算精度更高仅存储局部轮廓线状态时空复杂度更优是 12 * 12 及以内小规模网格计数问题的最优解法。二、核心解题思路当题目网格中存在上下、左右相邻格子的放置限制、禁止相邻选取等约束条件时可优先使用 轮廓线 DP。本文将结合经典例题 P1879 [USACO06NOV] Corn Fields G 完整讲解算法原理与实现。2.1 状态设计定义记忆化 DP 数组 dp[i][j][s]其中 i,j 为当前遍历的网格坐标下标从 0 开始s 为轮廓线状态压缩值。状态释义s 的第 0 ~ j-1 位记录当前第 i 行已遍历列的格子状态s 的第 j 位及后续位数记录上一行i-1 行对应列的格子状态。数组存储对应位置、对应轮廓线状态下的合法方案总数。为方便理解状态转移逻辑结合网格状态示例进行说明0 列 1 列 2 列 3 列 4 列 5 列 6 列0 行 1 0 1 0 0 0 01 行 1 0 0 1 0 1 1遍历至不同坐标时轮廓线状态sss的取值如下在 i1,j0 时s1010000s1010000s1010000。在 i1,j1 时s1010000s1010000s1010000。在 i1,j2 时s1010000s1010000s1010000。在 i1,j3 时s1000000。在 i1,j4 时s1001000。在 i1,j5 时s1001000。在 i1,j6 时s1001010。在 i1,j7 时s1001011。2.2 完整代码实现为适配书写习惯代码中将题目输入的行列数进行互换最终代码可正常 AC 对应题目全文下标从 0 开始。// 全文使用 based-0#includeusing namespace std;#define mod 100000000int dp[15][15][5000];int k[15][15];int n,m;int set(int s,int i,int v) //设置状态{return v0?s(~(1i)):s|(1i);}int get(int s,int i) //获取状态{return (si)1;}int f(int i,int j,int s) //轮廓线DP{if(in)return 1; //全部dp完了证明此方案有效返回1if(jm)return f(i1,0,s); //下一行if(dp[i][j][s]!-1)return dp[i][j][s]; //记忆化int ans;ansf(i,j1,set(s,j,0))%mod; //不种草一定可以所以直接下一列if(((j0(!get(s,j-1))(!get(s,j)))||(j0(!get(s,j))))k[i][j]) //当且仅当上一行和左边一列状态为0没种菜且这个地方可以种草ans(ansf(i,j1,set(s,j,1)))%mod;return dp[i][j][s]ans; //记忆化}int main(){cinnm; //n和m互换for(int i0;in;i)for(int j0;jm;j)cink[i][j];for(int i0;in;i)for(int j0;jm;j)for(int p0;p(112);p)dp[i][j][p]-1; //标记为未访问coutf(0,0,0);return 0;}看到这里可能你还不太理解所以附上一个友情链接 。三、学习总结熟练掌握本文的状态设计思路与模板代码并独立通过两道配套例题即可掌握轮廓线 DP 的基础用法能够独立解决基础网格限制类计数问题。
