HDU 5838 Mountain

正文索引 [隐藏]

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5838

题目翻译

对于一张NM高度为1~NM,X为局部最低点,.为普通点,我们定义局部最低点为高度低于周围8个点的点

题解

状态压缩DP+容斥原理
我们从1~NM开始往这张图上面摆放数字,如果这个点是局部最低点,那么在这个点被摆放之前,我们不能摆放其周围的点。
所以我们定义F[i][ST]表示摆到了第i个数字,现在所有的局部最低点的状态时ST。
转移的时候我们分摆放到局部最低点的情况F[i+1][newST]+=F[i][ST],和摆放在非局部最低点的情况F[i+1][ST]+=F[i][ST]
(可以摆放的位置数量)
这样DP算出来的F[N*M][FullST]是保证其中规定为局部最低点的点符合的情况。
如此可能有一些不应该是局部最低点也变成局部最低点的情况也被重算了。
于是用DFS枚举所有局部最低点的情况,计算情况数,用容斥组合一下就可以了。

代码