题目
题目大意
给你一个二维的图，其中.代表完好，*代表有缺陷。
现在要在图上刻一个数字(8)，满足：
- 由两个矩形组成。
- 每个矩形中必须有空隙在内部，也就是说，至少为(3*3)的矩形。
- 上矩形的下面那条边和下矩形上面的那条边所在的直线重合，并且上面是下面的子集。
- 必须雕刻在完好的部分。
- 得分为上矩形和下矩形所围出的空隙面积的乘积。
求最大得分。
思考历程
见到这种题，首先当然是从暴力想起啦~
首先想到的是(O(n^7))的暴力……这就不用说了吧……
然后我开始想，枚举行(i)和列([l,r])，以它为中间的那条边，向下和向上延伸最多多少。
设(up_{i,l,r})表示(i)行([l,r])区间最多向上延伸到多少。如果能延伸（设值为(y)），必须要满足([y,i])行的(l)和(r)位置都是完好的，而且(yleq i-2)
还有设(dn_{i,l,r})，定义类似（向下）。
于是题目变成了(O(n^5))……
由于上面的是下面的子集，所以我们可以试着存下它所有子集的最大值。
设(f_{i,l,r})表示在(i)行，区间为([l,r])的子集，所围成的矩形的最大面积。
显然(f_{i,l,r})可以转移到(f_{i,l-1,r})和(f_{i,l,r+1})
（然后你就会发现(i)的这一维是可以省去的。）
于是题目就变成了(O(n^3))
然而这题卡空间很严重……
所以我不得不用了short
代码
using namespace std;
#include <cstdio>
#include <cstring>
#define N 310
#define INF 10000
inline int min(int a,int b){return a<b?a:b;}
inline int max(int a,int b){return a>b?a:b;}
int n;
char st[N][N];
short cf[N][N];
#define clean(i,l,r) (cf[i][r]-cf[i][l-1]==0)
#define bro(i,l,r) (st[i][l]=='.' && st[i][r]=='.')
short up[N][N][N],dn[N][N][N];
int f[N][N];
int main(){
scanf("%d",&n);
for (int i=1;i<=n;++i){
scanf("%s",st[i]+1);
for (int j=1;j<=n;++j)
cf[i][j]=cf[i][j-1]+(st[i][j]=='*');
}
for (int l=1;l<=n;++l)
for (int r=l+2;r<=n;++r){
up[1][l][r]=INF;
up[2][l][r]=INF;
for (int i=3;i<=n;++i){
if (!bro(i,l,r) || !bro(i-1,l,r) || !bro(i-2,l,r)){
up[i][l][r]=INF;
continue;
}
if (up[i-1][l][r]!=INF)
up[i][l][r]=up[i-1][l][r];
else if (clean(i-2,l,r))
up[i][l][r]=i-2;
else
up[i][l][r]=INF;
}
}
for (int l=1;l<=n;++l)
for (int r=l+2;r<=n;++r){
dn[n][l][r]=-INF;
dn[n-1][l][r]=-INF;
for (int i=n-2;i>=1;--i){
if (!bro(i,l,r) || !bro(i+1,l,r) || !bro(i+2,l,r)){
dn[i][l][r]=-INF;
continue;
}
if (dn[i+1][l][r]!=-INF)
dn[i][l][r]=dn[i+1][l][r];
else if (clean(i+2,l,r))
dn[i][l][r]=i+2;
else
dn[i][l][r]=-INF;
}
}
int ans=-1;
for (int i=3;i<=n;++i){
for (int l=1;l+3-1<=n;++l){
int r=l+3-1;
if (clean(i,l,r) && up[i][l][r]!=-INF)
f[l][r]=i-up[i][l][r]-1;
else
f[l][r]=0;
}
for (int len=4;len<=n;++len)
for (int l=1;l+len-1<=n;++l){
int r=l+len-1;
f[l][r]=(clean(i,l,r) && up[i][l][r]!=-INF?int(i-up[i][l][r]-1)*(len-2):0);
f[l][r]=max(f[l][r],max(f[l+1][r],f[l][r-1]));
}
for (int l=1;l<=n;++l)
for (int r=l+2;r<=n;++r)
if (clean(i,l,r) && dn[i][l][r]!=-INF)
ans=max(ans,f[l][r]*(dn[i][l][r]-i-1)*(r-l-1));
}
printf("%d
",ans);
return 0;
}
总结
见到这种题……DP就好啦……