hdu 1505 (행렬 dp)

문제풀이 사고방식: 이 문제는 1506의 강화판이다. 처리 과정에서 모든 F를 1로 바꾸고 R을 0으로 한다. dp[i][j]는 i행을 표시하고 j열의 수 위에 몇 개의 연속적인 1이 있는지 정의하면 1506과 성공적으로 관계를 맺을 수 있다.
i행에서 1-m열에는 dp[i][j]가 있는데 이것은 i행의 직사각형 줄에 대한 합병이 아닌가.
이 문제는 정말 교묘하다. 나는 처음에 그것을 가장 큰 서브 행렬의 원형으로 여겼다. 모든 R의 부위는 무한히 작고 F는 1이다. 이렇게 해서 가장 큰 전 1행렬을 찾았는데 결과는 시간이 초과되었다.
내 TLE:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxn = 1005;
const int inf = 1e6+1;
int n,m,mat[maxn][maxn],sum[maxn][maxn];
char str[maxn<<2];

int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		getchar();
		for(int i = 1; i <= n; i++)
		{
			gets(str+1);
			for(int j = 1, k = 1; j <= m; j++, k += 2)
			{
				if(str[k] == 'R')
					mat[i][j] = -inf;
				else mat[i][j] = 1;
				sum[i][j] = sum[i][j-1] + mat[i][j];
			}
		}
		int ans = 0;
		for(int i = 1; i <= m; i++)
			for(int j = i; j <= m; j++)
			{
				int tmp = 0;
				for(int k = 1; k <= n; k++)
				{
					tmp += sum[k][j] - sum[k][i-1];
					if(ans < tmp) ans = tmp;
					if(tmp < 0) tmp = 0;
				}
			}
		printf("%d
",ans*3);
	}
	return 0;
}

AC:

#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxn = 1005;
int n,m,dp[maxn][maxn],l[maxn],r[maxn];
char str[2];

int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		getchar();
		memset(dp,0,sizeof(dp));
		for(int i = 1;i <= n; i++)  
           for(int j = 1; j <= m; j++)  
            {  
                scanf("%s",str);  
                if(str[0] == 'F')  
                    dp[i][j] = dp[i-1][j] + 1;  
            }  
		int tmp,ans = 0;
		for(int i = 1; i <= n; i++)
		{
			l[1] = 1, r[m] = m;
			for(int j = 2; j <= m; j++)
			{
				if(dp[i][j] == 0) continue;
				tmp = j;
				while(tmp > 1 && dp[i][tmp-1] >= dp[i][j]) tmp = l[tmp-1];
				l[j] = tmp;
			}
			for(int j = m - 1; j >= 1; j--)
			{
				if(dp[i][j] == 0) continue;
				tmp = j;
				while(tmp < m && dp[i][tmp+1] >= dp[i][j]) tmp = r[tmp+1];
				r[j] = tmp;
			}
			for(int j = 1; j <= m; j++)
			{
				if(dp[i][j] == 0) continue;
				tmp = (r[j] - l[j] + 1) * dp[i][j];
				if(tmp > ans)
					ans = tmp;
			}
		}
		printf("%d
",3*ans);
	}
	return 0;
}