【问题描述】
莫队长想要做一件超人衣服，大家都知道超人衣服中有一个很大的黄色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
|
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 |
// <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; } |
说点什么