NOI Newnode模拟题第二题 DP 单调性优化三分法

本文主要是介绍NOI Newnode模拟题第二题 DP 单调性优化三分法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第二题

【问题描述】

小火车虽然很穷，但是他还是得送礼物给妹子，所以他前往了二次元寻找不需要钱的礼物。小火车准备玩玩二次元的游戏，游戏当然是在一个二维网格中展开的，网格大小是n*m的，某些格子是好的，其余的则是不好的。每次你可以选择最底层（也就是第n层）的某两个相邻的列，并消掉最底下的至多三个格子，并且这两列都得有格子被消掉（也就是L型或者反着的L型），消掉格子以后上面的格子会掉落下来。当然最上面的空位会用不好的格子填满。小火车想得到所有的好格子送给妹子，请问至少得消多少次呢？

【输入格式】

第一行两个整数n,m，表示网格大小。接下来n行每行一个长度为m的字符串，表示这个网格，如果为*则是好格子，为#就不是。

【输出格式】

一行一个整数表示答案。

【数据范围与约定】

对于20%的数据n,m<=5；
对于50%的数据满足n,m<=500；
对于100%的数据满足2<=n,m<=2000。

首先容易想到把原题目转化为：用两种L把每一列的最上面的*消掉，求至少消多少次。

进一步转化：
把每一列最上面的*的位置写成一个数列 $A[i]$ ，每次操作可以使得数列里相邻的两个数其中一个减去1,另一个减去2.求把这个数列中全部数字变为非正数的最小操作数。

结合数据范围，不难想到采用DP的方式解决。

由于每一个元素的消去，只与在自己和左右两边相邻的元素上进行的操作有关，那么定义 $f[i][j]$ 为已经将 $i-1$ 及以前的所有数字变为非正数，且第 $i$ 列目前的数字是 $j$ 的最小操作数。那么目前只需要考虑在消去 $i$ 位上的数字时对第 $i+1$ 位的影响就可以转移了。

预处理一个数组 $g[i][j]$ ，表示把两个数字 $i,j$ 消去的最小操作数。那么有：

f [i + 1] [j] = m i n {f [i] [k] + g [A [i + 1] - j] [k]}

$f[i+1][j]=min\{f[i][k]+g[A[i+1]-j][k]\}$
其中

g[i][j] g [ i ] [ j ] $g[i][j]$ 可以

O(n2) O ( n 2 ) $O(n^2)$ 预处理：

g [i] [j] = m i n {g [i - 2] [j - 1], g [i - 1] [j - 2], g [i - 1] [j - 1]} + 1

$g[i][j]=min\{g[i-2][j-1],g[i-1][j-2],g[i-1][j-1]\}+1$
然后发现弄出

f f $f$ 的时间复杂度是

O (n^{3})

$O(n^3)$ 的，考虑优化这个DP。

考虑 $f,g$ 各有什么性质。对于 $g$ ，根据其含义，显然有：

g [i] [j + 1] \geq g [i] [j]

$g[i][j+1]\geq g[i][j]$
对于

f f $f$ ,有：

f [i] [j] \geq f [i] [j + 1]

$f[i][j]\geq f[i][j+1]$
也比较显然，剩得越多，消的次数肯定不会更多嘛。

回过头来看DP方程：

f [i + 1] [j] = m i n {f [i] [k] + g [A [i + 1] - j] [k]}

$f[i+1][j]=min\{f[i][k]+g[A[i+1]-j][k]\}$
枚举

i,j i , j $i,j$ 显然是无法优化的，要优化就要考虑优化枚举

k k $k$ .根据上面的分析，注意到在

k

$k$ 不断增大的过程中，

f[i][k] f [ i ] [ k ] $f[i][k]$ 单调不升，而

g[A[i+1]−j][k] g [ A [ i + 1 ] − j ] [ k ] $g[A[i+1]-j][k]$ 单调不减，那么

f[i][k]+g[A[i+1]−j][k] f [ i ] [ k ] + g [ A [ i + 1 ] − j ] [ k ] $f[i][k]+g[A[i+1]-j][k]$ 就是一个关于

k k $k$ 的单峰函数！单峰函数的极值可以用三分法处理。

整数的三分好像不是很好……我采用的是在 $r-l$ 小于一定值之后暴力更新答案。采用三分法的话，这个值给得小就会错。

有不用三分的优秀做法：http://blog.csdn.net/Mogician_Evian/article/details/79474362

代码写得比较丑。

#include<stdio.h>
#include<cstring>
#include<algorithm>
#define MAXN 2005
using namespace std;int N,M,A[MAXN],f[MAXN][MAXN],g[MAXN][MAXN];
char Map[MAXN][MAXN];int main(){int i,j,k,l,r,lmid,rmid,t,id;scanf("%d%d",&N,&M);for(i=1;i<=N;i++)scanf("%s",&Map[i][1]);for(i=1;i<=M;i++){for(j=1;j<=N;j++)if(Map[j][i]=='*'){A[i]=N-j+1;break;}}memset(g,60,sizeof(g));memset(f,60,sizeof(f));g[0][0]=0;for(i=1;i<=N;i++)g[i][0]=g[0][i]=(i+1)/2;for(i=1;i<=N;i++)for(j=1;j<=N;j++){if(i>1)g[i][j]=min(g[i][j],g[i-2][j-1]+1);if(j>1)g[i][j]=min(g[i][j],g[i-1][j-2]+1);g[i][j]=min(g[i][j],g[i-1][j-1]+1);}f[1][A[1]]=0;for(i=1;i<=M;i++){if(i==1){for(j=0;j<=A[i+1];j++)for(k=0;k<=A[i];k++)f[i+1][j]=min(f[i+1][j],f[i][k]+g[A[i+1]-j][k]);continue;}for(j=0;j<=A[i+1];j++){l=0;r=A[i];while(l<=r){if(r-l<=25){for(k=l;k<=r;k++)f[i+1][j]=min(f[i+1][j],f[i][k]+g[A[i+1]-j][k]);break;}lmid=(r-l)/3+l;rmid=(r-l)/3+lmid;if(f[i][lmid]+g[A[i+1]-j][lmid]<f[i][rmid]+g[A[i+1]-j][rmid])r=rmid;else if(f[i][lmid]+g[A[i+1]-j][lmid]>f[i][rmid]+g[A[i+1]-j][rmid])l=lmid;else l=lmid,r=rmid;}}}printf("%d\n",f[M+1][0]);
}