Ｎewnode‘s NOI 模拟赛 第二题 （单调dp）

发表于 |
字数统计: 836字 | 阅读时长 ≈ 4min

第二题

问题描述

这里写图片描述

样例输入 1

3 2
*#
#*
##

样例输出 1

2

样例输入 2

4 5
*####
*####
####
#\**#

样例输出 2

3

提示

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

题意要求用每次消去正或反的Ｌ形的三个格子，消除所有的关键格子，需要的最小步数。
显然每一列只需要关心最上面一个关键格子的位置就行了。
因此令$A[i]$表示第$i$列最上面一个关键格子是从下往上数的第几个格子。

先考虑暴力的dp，令$F[i][j]$表示前$i$列，前$i-1$列已经消完，第$i$列还需要消$j$个格子的最优步数。
那么转移的时候枚举第$i$列消去了$k$个反Ｌ形，有
$$
F[i][j]=min(F[i-1][k+2(A[i]-j-2k)]+k+A[i]-j-2k)
$$
$k+2(A[i]-j-2k)$表示消去第$i$行时，第$i-1$行会被消去的数量，也可以从$F[i-1]$第二维更小的位置转移过来，但显然不会更优。另外，$F[i][A[i]+1]-F[i][n]$都赋值为$F[i-1][0]$

这个dp是$O(n^3)$的，需要优化。

考虑一下每次转移时$F[i][j]$和$F[i][j+1]$分别在$k$等于多少时取得最优值，一个结论是$F[i][j+1]$取得最优值的$k$一定小于等于$F[i][j]$取得最优值的k，这个结论脑补一下就能理解。因为需要消去的块变少了，那么相应的操作数一定是不增的。

容易得到$F[i]$是随着j变大而单调不增的。

再观察一下可以发现，在$j$确定的时候，$F[i-1][2A[i]-2j-3k]+A[i]-j-k$的取值是单峰的。因为$F[i-1][2A[i]-2j-3k]$随k的减小是不增的，$A[i]-j-k$是单增的，因此它是单峰的。

那么我们得到了一个很好的性质，即$F[i][j]$的转移是单峰的，并且峰的位置是单调的。
因此我们就可以将枚举k的复杂度变成均摊$O(1)$的了。只需要每次记录一下最优的k取值，讨论$j+1$时直接从这个最优取值开始，如果$k-1$不能更优就$break$就行了。

总时间复杂度$O(n^2)$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 2005
using namespace std;
int n,m,F[N][N],A[N];
char map[N][N];
int main()
{
	int i,j,k,x,id;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)scanf("\n%s",&map[i][1]);
	for(i=1;i<=m;i++)
	{
		for(j=1;j<=n;j++)if(map[j][i]=='*')break;
		A[i]=n+1-j;
	}
	memset(F,60,sizeof(F));
	for(i=0;i<=n;i++)F[0][i]=0;
	for(i=1;i<=m;i++)
	{
		id=A[i]>>1;
		for(j=0;j<=A[i];j++)
		{
			id=min(id,A[i]-j>>1);
			for(k=id;k>=0;k--)
		    {
			    x=k+(A[i]-j-2*k<<1);
			    if(x>A[i-1])x=A[i-1];
			    if(F[i][j]>=F[i-1][x]+A[i]-j-k)id=k,F[i][j]=F[i-1][x]+A[i]-j-k;
				else break;
		    }
		}
		for(j=A[i]+1;j<=n;j++)F[i][j]=F[i-1][0];
	}
	printf("%d",F[m][0]);
}