题解 P4147 【玉蟾宫】

发表于 | 更新于 | 阅读次数：

昨天晚上刚学悬线法。

我们对于题目给定的矩阵

设R为障碍，那么是不是其他连续的一段‘F’我们都可以看成一块？

用left和right分别表示这一行这一列的边界，我们把它覆盖成一段，

用up来表示是否能从上方延伸下来，然后考虑怎么延伸。

如果能从上方转移，那么，是不是要取这两段的公共部分。

我们在转移以后每次求出ans的最大值即可。

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
86
87
88
89
90
91
92
93
94
95
96
97
#include<bits/stdc++.h>
using namespace std;
int n,m;
int l[1001][1001],r[1001][1001],up[1001][1001];
char s[1001][1001];
int ans;
void read(int &x)
{
	x=0;
	char ch=getchar();
	int pd=1;
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
		{
			pd=-pd;
		}
		ch=getchar();
	}
	while(ch<='9'&&ch>='0')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	x*=pd;
}
void write(const int &x)
{
	char f[100001];
	int s=0;
	int tmp=x;
	if(tmp<0)
	{
		tmp=-tmp;
		putchar('-');
	}
	while(tmp>0)
	{
		f[s++]=tmp%10+'0';
		tmp/=10;
	}
	while(s>0)
	{
		putchar(f[--s]);
	}
}
int main()
{
	read(n);
	read(m);
	char ch;
	for(register int i=1;i<=n;++i)
	{
		for(register int j=1;j<=m;++j)
		{
			cin>>s[i][j];
			l[i][j]=j;
			r[i][j]=j;
			up[i][j]=1;
		}
	}
	for(register int i=1;i<=n;++i)
	{
		for(register int j=2;j<=m;++j)
		{
			if(s[i][j]=='F'&&s[i][j-1]=='F')
			{
				l[i][j]=l[i][j-1];
			}
		}
	}
	for(register int i=1;i<=n;++i)
	{
		for(register int j=m-1;j>=1;--j)
		{
			if(s[i][j]=='F'&&s[i][j+1]=='F')
			{
				r[i][j]=r[i][j+1];
			}
		}
	}
	for(register int i=1;i<=n;++i)
	{
		for(register int j=1;j<=m;++j)
		{
			if(i>1&&s[i][j]=='F'&&s[i-1][j]=='F')
			{
				up[i][j]=up[i-1][j]+1;
				l[i][j]=max(l[i][j],l[i-1][j]);
				r[i][j]=min(r[i-1][j],r[i][j]);
			}
			int ss=(up[i][j]*(r[i][j]-l[i][j]+1));
			ans=max(ss*3,ans);
		}
	}
	write(ans);
}

这是悬线法的模板题，可以从这道题入手（反正没人看怎么话这么多）