hdu 2870 Largest Submatrix （DP)

Largest Submatrix

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 1534    Accepted Submission(s): 735

Problem Description Now here is a matrix with letter 'a','b','c','w','x','y','z' and you can change 'w' to 'a' or 'b', change 'x' to 'b' or 'c', change 'y' to 'a' or 'c', and change 'z' to 'a', 'b' or 'c'. After you changed it, what's the largest submatrix with the same letters you can make?  

Input The input contains multiple test cases. Each test case begins with m and n (1 ≤ m, n ≤ 1000) on line. Then come the elements of a matrix in row-major order on m lines each with n letters. The input ends once EOF is met.  

Output For each test case, output one line containing the number of elements of the largest submatrix of all same letters.  

Sample Input

2 4
abcw
wxyz
        

Sample Output

3
        

又是一個悲傷的故事，做了一上午

，其實就是和1505和1506一樣，這題枚舉一下a，b，c，就行了，不知為什麼酒一直wa，看别人的題解，沒有用我這種方法的，都是記一下最左邊大于等于它的位置，和右邊大于等于它的位置，和我的方法在原理上是一樣的，我是記左邊大于等于它的位置，右邊大于等于它的位置，debug了半天才發現把m打成了n。

代碼：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=1000+100;
char s[maxn][maxn];
int a[maxn][maxn];
int dpl[maxn],dpr[maxn];
int n,m;
int ans;
void solve(char c,char w,char x,char y)
{
    for(int i=1;i<=n;i++)
    {
        a[i][0]=a[i][m+1]=-1;
        for(int j=1;j<=m;j++)
        {
            if(s[i][j]==c||s[i][j]==w||s[i][j]==x||s[i][j]==y)
            {
                if(i>1)
                a[i][j]=a[i-1][j]+1;
                else
                {
                    a[i][j]=1;
                }
            }
            else
            {
                a[i][j]=0;
            }
        }
       int temp;
       memset(dpl,0,sizeof(dpl));
       memset(dpr,0,sizeof(dpr));
       dpl[1]=1;
       dpr[m]=1;
       for(int j=2;j<=m;j++)
       {
           int k;
           dpl[j]=1;
           if(a[i][j])
           {
               k=j;
               while(a[i][j]<=a[i][k-1])
               {
                   dpl[j]+=dpl[k-1];
                   k-=dpl[k-1];
               }
               // while(a[i][dpl[j]-1]>=a[i][j])
               //  dpl[j]=dpl[dpl[j]-1];
           }
       }
       for(int j=m-1;j>=1;j--)
       {
           int k;
           dpr[j]=1;
           if(a[i][j])
           {
               k=j;
               while(a[i][j]<=a[i][k+1])
               {
                   dpr[j]+=dpr[k+1];
                   k=k+dpr[k+1];
               }
               // while(a[i][dpr[j]+1]>=a[i][j])
               //   dpr[j]=dpr[dpr[j]+1];
           }
       }
       for(int j=1;j<=m;j++)
       {
           if(a[i][j])
           {
           temp=a[i][j]*(dpr[j]+dpl[j]-1);
          // temp=a[i][j]*(dpr[j]-dpl[j]+1);
           if(ans<temp)
           ans=temp;
           }
       }
    }
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%s",s[i]+1);
        }
        ans=0;
        solve('a','w','y','z');
        solve('b','w','x','z');
        solve('c','x','y','z');
        printf("%d\n",ans);
    }
    return 0;
}