dp 练手题 题解

题面

题面：

在盖了一所正方形房子后，FJ 最近又得到了一块正三角形的土地，他也想在这块土地上建造一所房子，这次这个房子也必须是正三角形的。但是，这块土地并非十全十美，上面有很多不平坦的地方（也可以叫瑕疵）。这些瑕疵十分恶心，以至于根本不能在上面盖一砖一瓦。他希望找到一块最大的正三角形无瑕疵土地来盖房子。不过，这并不是什么难题，FJ 在 \(1\) 秒内就轻松解决了这个问题。现在，您也来试试吧。

如图所示，黑色的小正三角形表示瑕疵。

输入：

第一行，一个整数 \(n\)，表示土地纵向划分为 \(n\) 行。

（\(n\le 1000\)）

接下来的 \(n\) 行，第 \(i\) 行包括了 \((n−i)\times 2+1\) 个有效字符。

- 表示这块土地是好的，# 表示这块土地有瑕疵。

为了保持三角形的形状，输入文件中会出现空格。

输出：

一行一个整数，表示最大的正三角形包括的小三角形数。

样例输入：

5
#-##----#
 -----#-
  ---#-
   -#-
    -

样例输出：

9

我相信很多人和我一样看这题会想用二维前缀和做。

我试过了，比较麻烦。

下面介绍一种 DP 的方法。

思路

有两种三角形，正的（尖朝下），或者反的（尖朝上）。

我们设计状态：

a[i][j]，以第 \(i\) 行，第 \(j\) 列为底三角形的最大可用三角形边长（\(j\bmod 2=1\)）；

b[i][j]，以第 \(i\) 行，第 \(j\) 列为顶三角形的最大可用三角形边长（\(j\bmod 2=0\)）。

正的

我们看 \(x\) 这个小三角形。

如果它是瑕疵，直接 a[i][j]=0。

否则，可以从 \(y,z\) 转移过来，那么显然转移式子是：

a[i][j]=min(a[i-1][j],a[i-1][j+2])*(mp[i-1][j+1]=='-')+1;

mp 是存整个地图的数组。

另，我们的存储方式是：把所有三角形看成一个个点，然后往左压，具体见代码。

反的

同理。

如果它是瑕疵，直接 b[i][j]=0。

否则，可以从下方转移过来，那么显然转移式子是：

b[i][j]=min(b[i+1][j-2],b[i+1][j])*(mp[i+1][j-1]=='-')+1;

所以行要从后向前遍历。

坑点

输入直接 cin。

要取所有状态的 max。

最后时求的是面积不是边长。

时间复杂度

\(O(n^2)\)，能过。

甚至 \(n\) 可以到一万。

代码

code

#include<stdio.h>
#include<bits/stdc++.h>
#define N 1000010
#define MOD 998244353
#define esp 1e-8
#define INF 999999999999999999
#define LL long long
#define rep(i,a,b,g) for(LL i=a;i<=b;i+=g)
#define rem(i,a,b,g) for(LL i=a;i>=b;i-=g)
#define repn(i,a,b,g) for(LL i=a;i<b;i+=g)
#define remn(i,a,b,g) for(LL i=a;i>b;i-=g)
#define pll pair<LL,LL>
#define mkp(x,y) make_pair(x,y)
#define i128 __int128
#define lowbit(x) ((x)&(-(x)))
#define lc (u<<1)
#define rc (u<<1|1)
using namespace std;
void read(i128 &x)
{
	i128 f=1;
	x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	x*=f;
}
void writing(i128 x)
{
	if(x>=10)writing(x/10);
	putchar(x%10+'0');
}
void write(i128 x)
{
	if(x<0)
	{
		cout<<'-';
		x=-x;
	}
	writing(x);
}
LL n;
LL a[1010][1010],b[1010][1010],mca,mcb;
char x,mp[1010][1010];
int main()
{
	cin>>n;
	rep(i,1,n,1)
	{
		rep(j,1,2*n-2*i+1,1)
		{
			cin>>x;
			mp[i][j]=x;
		}
	}
	rep(i,1,n,1)
	{
		rep(j,1,2*n-2*i+1,2)
		{
			if(mp[i][j]=='#')a[i][j]=0;
			else
			{
				a[i][j]=min(a[i-1][j],a[i-1][j+2])*(mp[i-1][j+1]=='-')+1;
			}
			mca=max(mca,a[i][j]);
		}
	}
	rem(i,n,1,1)
	{
		rep(j,2,2*n-2*i,2)
		{
			if(mp[i][j]=='#')b[i][j]=0;
			else
			{
				b[i][j]=min(b[i+1][j-2],b[i+1][j])*(mp[i+1][j-1]=='-')+1;
			}
			mcb=max(mcb,b[i][j]);
		}
	}
	cout<<max(mca,mcb)*max(mca,mcb)<<endl;
	return 0;
}

致谢

教练 zxc，提供题目；

同学 whl，提供思路；

同学 zxz，提出可能的时间复杂度（虽然没做出来）。