超人衣服 – 徐亦轲的博客

【问题描述】

莫队长想要做一件超人衣服，大家都知道超人衣服中有一个很大的黄色S，其余的部分都是红色的。现在这个衣服还没染色，但有些地方已经被溅到了红色染料。所以莫队长想要你在其余的空白地方找到一个面积最大的S。
整件衣服被划分为n*m个小块，一个S被定义为5笔，每一笔的长度和宽度都是不确定的正整数。如下图的A是一个合法的S，B不是一个合法的S。

【输入格式】

第一行两个数n，m。
接下来n行，每行m个数，第i行第j个数如果是0，表示这一块是空白，如果是1，表示这一块是红色。

【输出格式】

仅一个数，表示最大S的面积。

【数据范围】

对于20%的数据，5≤n,m≤10
对于100%的数据，5≤n,m≤100

【题解】

这道题听说是【NOI2013书法家】改过来的

这道题相对简单（不过一开始我不会做）

可以讲一个“S”横向切割分成五个部分：上面的横，左面的竖，中间的横，右面的竖，下面的横

那么就可以进行DP：dp[i][l][r][k]表示第i行l~r为第k个部分时的最优值

打代码也是打得很爽呢233

// <super.cpp> - 03/05/16 08:05:57
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
	int res=0,fh=1;char ch=getchar();
	while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
	if(ch=='-')fh=-1,ch=getchar();
	while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
	return fh*res;
}
#define up(a,b) if(b)a=max(a,r-l+1+b)
const int MAXN=101;
int a[MAXN][MAXN],d[MAXN][MAXN];
int dp[MAXN][MAXN][MAXN][5];
int main(){
	freopen("super.in","r",stdin);
	freopen("super.out","w",stdout);
	int n=getint(),m=getint();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)a[i][j]=getint(),d[i][j]=d[i][j-1]+a[i][j];
	int ans=0;
	for(int i=1;i<=n;i++)
		for(int l=1;l<=n;l++)
			for(int r=l;r<=n;r++){
				if(d[i][r]-d[i][l-1])continue;
				dp[i][l][r][0]=r-l+1+dp[i-1][l][r][0];
				up(dp[i][l][r][1],dp[i-1][l][r][1]);
				up(dp[i][l][r][2],dp[i-1][l][r][2]);
				up(dp[i][l][r][3],dp[i-1][l][r][3]);
				up(dp[i][l][r][4],dp[i-1][l][r][4]);
				for(int rr=r+1;rr<=n;rr++)up(dp[i][l][r][1],dp[i-1][l][rr][0]);
				for(int rr=r-1;rr>=l;rr--)up(dp[i][l][r][2],dp[i-1][l][rr][1]);
				for(int ll=l-1;ll>=1;ll--)up(dp[i][l][r][3],dp[i-1][ll][r][2]);
				for(int ll=l+1;ll<=r;ll++)up(dp[i][l][r][4],dp[i-1][ll][r][3]);
				ans=max(ans,dp[i][l][r][4]);
			}
	printf("%d",ans);
	return 0;
}

// <super.cpp> - 03/05/16 08:05:57

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int getint(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

#define up(a,b) if(b)a=max(a,r-l+1+b)

const int MAXN=101;

int a[MAXN][MAXN],d[MAXN][MAXN];

int dp[MAXN][MAXN][MAXN][5];

int main(){

freopen("super.in","r",stdin);

freopen("super.out","w",stdout);

int n=getint(),m=getint();

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++)a[i][j]=getint(),d[i][j]=d[i][j-1]+a[i][j];

int ans=0;

for(int i=1;i<=n;i++)

for(int l=1;l<=n;l++)

for(int r=l;r<=n;r++){

if(d[i][r]-d[i][l-1])continue;

dp[i][l][r][0]=r-l+1+dp[i-1][l][r][0];

up(dp[i][l][r][1],dp[i-1][l][r][1]);

up(dp[i][l][r][2],dp[i-1][l][r][2]);

up(dp[i][l][r][3],dp[i-1][l][r][3]);

up(dp[i][l][r][4],dp[i-1][l][r][4]);

for(int rr=r+1;rr<=n;rr++)up(dp[i][l][r][1],dp[i-1][l][rr][0]);

for(int rr=r-1;rr>=l;rr--)up(dp[i][l][r][2],dp[i-1][l][rr][1]);

for(int ll=l-1;ll>=1;ll--)up(dp[i][l][r][3],dp[i-1][ll][r][2]);

for(int ll=l+1;ll<=r;ll++)up(dp[i][l][r][4],dp[i-1][ll][r][3]);

ans=max(ans,dp[i][l][r][4]);

}

printf("%d",ans);

return 0;

}