15.10.01【单调队列、二分答案、记忆化搜索】

OI&ACM, OI训练
  1. 1.为了和谐 (square)
    1. 方法一：
    2. 方法二：
    3. 方法三：
  2. 2.防守之道 (cover)
  3. 3.分蛋糕(separation)

1.为了和谐 (square)

【问题背景】 在机房里，有两只小可爱，一只大可爱，一只小可爱。其中大可爱对大的东西感兴趣，小可爱对小的东西感兴趣。 现在有一个 \(a \times b\) 的矩阵，矩阵中每个位置都有一个非负整数\(i（0<=i<=2 000 000 000）\)，两只小可爱要在这个矩阵中选择一个\(n\times n\)的正方形，大可爱要正方形中的最大数，小可爱要正方形中的最小数。 但是，如果两个人的数字差距过大的话，就会造成矛盾……为了机房人民的和谐相处，请你帮他们选择这个正方形，使得这个差距最小。 【问题描述】 有一个\(a\times b\)的整数组成的矩阵，现请你从中找出一个\(n\times n\) 的正方形区域，使得该区域所有数中的最大值和最小值的差最小。

方法一：

\(20\)分水过。

方法二：

由RMQ问题，联想到ST算法，很好，能想到这个已经很不错了。自己随便搞一个二维的ST算法，\(O(AB lb n)\)，卡着时限轻松飘过。

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=1001,MAXS=101,LG=6,INF=0x7FFFFFFF;
using namespace std;
int N,M,P,Ans;
int F[MAXN][MAXN][LG],G[MAXN][MAXN][LG];
void init()
{
    int i,j;
    freopen("square.in","r",stdin);
    freopen("square.out","w",stdout);
    scanf("%d%d%d",&N,&M,&P);
    for (i=1;i<=N;i++)
        for (j=1;j<=M;j++)
        {
            scanf("%d",&F[i][j][0]);
            G[i][j][0]=F[i][j][0];
        }
    Ans=INF;
}
inline int Min(int a,int b){return a<b?a:b;}
inline int Max(int a,int b){return a>b?a:b;}
void SparseTable()
{
    int i1,i2,j,jt,max,min;
    for (j=jt=1;jt<=P;j++,jt=jt<<1)
    {
        for (i1=1;i1+jt<=N;i1++)
        {
            for (i2=1;i2+jt<=M;i2++)
            {
                max=0;min=INF;
                max=Max(max,F[i1][i2][j-1]);
                max=Max(max,F[i1][i2+jt][j-1]);
                max=Max(max,F[i1+jt][i2][j-1]);
                max=Max(max,F[i1+jt][i2+jt][j-1]);
                F[i1][i2][j]=max;
                min=Min(min,G[i1][i2][j-1]);
                min=Min(min,G[i1][i2+jt][j-1]);
                min=Min(min,G[i1+jt][i2][j-1]);
                min=Min(min,G[i1+jt][i2+jt][j-1]);
                G[i1][i2][j]=min;
            }
        }
    }
}
int Log2(int a)
{
    int r;
    for (r=0;(1<<r)<=a;r++);
    return r-1;
}
void solve()
{
    int i,j,k,kt,min,max;
    k=Log2(P);
    kt=1<<k;
    for (i=1;i+P-1<=N;i++)
    {
        for (j=1;j+P-1<=M;j++)
        {
            max=0;min=INF;
            max=Max(max,F[i][j][k]);
            max=Max(max,F[i][j+P-kt][k]);
            max=Max(max,F[i+P-kt][j][k]);
            max=Max(max,F[i+P-kt][j+P-kt][k]);
            min=Min(min,G[i][j][k]);
            min=Min(min,G[i][j+P-kt][k]);
            min=Min(min,G[i+P-kt][j][k]);
            min=Min(min,G[i+P-kt][j+P-kt][k]);
            Ans=Min(Ans,max-min);
        }
    }
}
int main()
{
    init();
    SparseTable();
    solve();
    printf("%d\n",Ans);
    return 0;
}

方法三：

看见这种区间移动的RMQ问题，相信大家都能想到“单调队列”吧？（想不到的自行面壁！……） 那么问题来了！二维的怎么搞?！ 首先只看一层，可以用单调队列搞出来从每个点开始往后n个数的极值，如图。 用同样的方法将每一行都处理出来，并用数组\(w[i][j]\)记录第\(i\)行，从第\(j\)个开始往后\(n\)个数的最大值，\(ww[i][j]\)记录最小值。 接下来再来纵看，但看其中一列，也用同样的方法以\(w\)和\(ww\)数组为依据来搞单调队列，如图 因为w已经将横向长为\(n\)的最大值存储在左边的\(4\)个点中了，纵向再求出这\(4\)个点的最大值，就是这\(4*4\)的矩阵的最大值。 最后再枚举一下正方形的左上定点，求出结果。\(O(ab+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
39
40
41
42
43
44
45
46
47
48
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
const int N=1001;
struct node{
	int pos,x;
}max[N],min[N];
int h1,t1,h2,t2;
int a[N][N],w[N][N],ww[N][N];
int main(){
	freopen("square.in","r",stdin);
	freopen("square.out","w",stdout);
	int aa,bb,n;
	scanf("%d%d%d",&aa,&bb,&n);
	for(int i=1;i<=aa;i++)
		for(int j=1;j<=bb;j++) scanf("%d",&a[i][j]);
	for(int j=1;j<=aa;j++){
		h1=h2=1; t1=t2=0;
		for(int i=1;i<=bb;i++){
			if(h1<=t1 && max[h1].pos<i-n+1) h1++;
			if(h2<=t2 && min[h2].pos<i-n+1) h2++;
			while(h1<=t1 && max[t1].x<a[j][i]) t1--;
				max[++t1].pos=i; max[t1].x=a[j][i];
			while(h2<=t2 && min[t2].x>a[j][i]) t2--;
				min[++t2].pos=i; min[t2].x=a[j][i];
			if(i-n+1>0) w[j][i-n+1]=max[h1].x,ww[j][i-n+1]=min[h2].x;
		}
	}
	for(int j=1;j<=bb-n+1;j++){
		h1=h2=1; t1=t2=0;
		for(int i=1;i<=aa;i++){
			if(h1<=t1 && max[h1].pos<i-n+1) h1++;
			if(h2<=t2 && min[h2].pos<i-n+1) h2++;
			while(h1<=t1 && max[t1].x<w[i][j]) t1--;
				max[++t1].pos=i; max[t1].x=w[i][j];
			while(h2<=t2 && min[t2].x>ww[i][j]) t2--;
				min[++t2].pos=i; min[t2].x=ww[i][j];
			if(i-n+1>0) w[i-n+1][j]=max[h1].x,ww[i-n+1][j]=min[h2].x;
		}
	}
	int ans=0x7fffffff;
	for(int i=1;i<=aa-n+1;i++)
		for(int j=1;j<=bb-n+1;j++)
		if(w[i][j]-ww[i][j]<ans) ans=w[i][j]-ww[i][j];
	printf("%d\n",ans);
	return 0;
}

2.防守之道 (cover)

【问题背景】 17班又要和AP1班踢足球了，为了吸取上次惨败的教训，王甫 王美男决定这次要好好加强一下防御。甫哥觉得，2个后卫防守实在不给力，决定变成3个防守后卫。 假定AP1班有n个前锋，每个前锋经常活动的区域是一个点，而3名后卫的防守区域都是一个边长为l的正方形。 甫哥想知道，l最小多大时，可以保证每名前锋都在防守区域内。 【问题描述】 给定n个点的坐标，求最小的l，使得3个边长为l的正方形可以将这n个点全部覆盖（每个正方形的各边平行于x轴和y轴）。

看见题目，应该就能想到是考察“二分答案”的吧？想不到的继续面壁！…… 问题的关键是，给定l，如何判断能否将n个点全覆盖？ 先思考这样一个问题，根据n个点的坐标，可以处理出这n个点的外接矩形，那么，现在给你一个边长为l的正方形，如何放置?
答案是肯定的，一定是放在这个外接矩形的4个角！能想明白吗？为了全覆盖，只能放在4个角。 那么问题就好说了，先放一个正方形，没有覆盖的点再次处理出外接矩形，然后再放一个正方形，没有覆盖的点再处理出外接矩形，判断最后的外接矩形的长和正方形边长的大小关系，就知道是否可以覆盖了。 至于实现，由于每次放正方形都有4个位置，所以写DFS就行了，至于深度，由于只有2，所以完全不用担心。 最终效率 O(n lb L)，轻松AC

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<iostream>
#include<cstring>
#include<cstdio>
const int inf=2000000000;
int n,yes,l,r,mid;
int x[20001],y[20001];
bool b[20001];
using namespace std;
void dfs(int num,int len)
{
	if(num>3)
	{
		for(int i=1;i<=n;i++)
		  if(!b[i]) return;
		yes=1;return;
	}
	int maxx=-inf,maxy=-inf,minx=inf,miny=inf;
	for(int i=1;i<=n;i++)
	if(!b[i])
	{
		if(x[i]>maxx) maxx=x[i];if(x[i]<minx) minx=x[i];
		if(y[i]>maxy) maxy=y[i];if(y[i]<miny) miny=y[i];
	}
	bool a[20001];
	memcpy(a,b,sizeof(a));
	
	for(int i=1;i<=n;i++)
	if(x[i]>=maxx-len&&y[i]>=maxy-len) b[i]=1;
	dfs(num+1,len);
	memcpy(b,a,sizeof(b));
	
	for(int i=1;i<=n;i++)
	if(x[i]<=minx+len&&y[i]>=maxy-len) b[i]=1;
	dfs(num+1,len);
	memcpy(b,a,sizeof(b));
	
	for(int i=1;i<=n;i++)
	if(x[i]<=minx+len&&y[i]<=miny+len) b[i]=1;
	dfs(num+1,len);
	memcpy(b,a,sizeof(b));
	
	for(int i=1;i<=n;i++)
	if(x[i]>=maxx-len&&y[i]<=miny+len) b[i]=1;
	dfs(num+1,len);
	memcpy(b,a,sizeof(b));
}
int main()
{
	freopen("cover.in","r",stdin);
	freopen("cover.out","w",stdout);
	scanf("%d",&n);
	int maxx=-inf,maxy=-inf,minx=inf,miny=inf;
	for(int i=1;i<=n;i++)  
	{
		scanf("%d%d",&x[i],&y[i]);
		if(x[i]>maxx) maxx=x[i];if(x[i]<minx) minx=x[i];
		if(y[i]>maxy) maxy=y[i];if(y[i]<miny) miny=y[i];
	}
	l=0;r=max(maxx-minx,maxy-miny);
	while(l!=r)
	{
		mid=(l+r)/2;
	    memset(b,0,sizeof(b));yes=0;
	    dfs(1,mid);
	    if(yes) r=mid;else l=mid+1;
	}
	printf("%d",l);
}

3.分蛋糕(separation)

【题目背景】 今天老师给机房的同志们买回a*b的蛋糕，蛋糕的每个位置都有 一个美味值。机房里有n位同学，现在要将整个蛋糕切n-1刀，分成n块，只能够沿着平行于蛋糕边缘的方向切割，每次切割将一块矩形蛋糕分成2块矩形蛋糕。对于切好的n块蛋糕，每块蛋糕都有一个美味值，等于内部所有美味值之和。为了尽可能的公平，希望这n块蛋糕美味值的标准差最小。 老师将切蛋糕的任务交给了楠哥，但是楠哥不会啊，快急哭了…… 现在他求助于你，希望你编写出一个程序，计算出这个最小的标准差值。 【题目描述】 对一个a*b的矩阵进行n-1次分割，使得分成的n个矩阵标准差最小，求出最小值（结果保留2位小数）

记忆化搜索 f[x1][y1][x2][y2][k]表示(x1,y1)到(x2,y2)的矩形分割成k个矩形的最优结果

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
39
40
41
42
43
44
45
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int a,b,n,x,tot;
int g[11][11],sum[11][11],f[11][11][11][11][11];
int search(int x1,int y1,int x2,int y2,int num)
{
	if(f[x1][y1][x2][y2][num]!=-1)  return f[x1][y1][x2][y2][num];
	if(num==1)  
	{
	   int x=sum[y1][y2]+sum[x1-1][x2-1]-sum[x1-1][y2]-sum[y1][x2-1];
	   return x*x;
	}
	int x=0x7ffffff;
	for(int i=x1;i<y1;i++)
	  for(int j=1;j<num;j++)
	  {
		int y=search(x1,i,x2,y2,j)+search(i+1,y1,x2,y2,num-j);
		if(y<x) x=y;
	  }
	for(int i=x2;i<y2;i++)
	  for(int j=1;j<num;j++)
	  {
		int y=search(x1,y1,x2,i,j)+search(x1,y1,i+1,y2,num-j);
		if(y<x) x=y;
	  }
	f[x1][y1][x2][y2][num]=x;
	return x;
}
int main()
{
	freopen("separation.in","r",stdin);
	freopen("separation.out","w",stdout);
	memset(f,-1,sizeof(f));
	scanf("%d%d%d",&a,&b,&n);
	for(int i=1;i<=a;i++)
	  for(int j=1;j<=b;j++)
	    scanf("%d",&g[i][j]),tot+=g[i][j];
	for(int i=1;i<=a;i++)
	  for(int j=1;j<=b;j++)
	    sum[i][j]=g[i][j]+sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];
	float x=1.0*search(1,a,1,b,n)/n-1.0*tot*tot/n/n;
	printf("%.2f",sqrt(x));
}