题目描述

题意：

给你一个n*n矩阵，你求出最大对称矩阵。
比如： （加粗）

a b x

c y b

z c a

当给的矩阵比较大的时候

a a a a a x

a a a a x a

a a a x a a ans=3

c a x a a a 中断

a x a a a a

x a a a a a

所以说我们想到可以用转移方程来解决这个问题

在稿纸上再画几笔我们可以得到：

(x为当前求得对称矩阵的边界，i为当前位置）

dp[i][j]=1 (i==0)

dp[i][j]=dp[i-1][j+1]+1; i-x>dp[i-1][j+1]

dp[i][j]=i-x;

于是代码为下

#include
using namespace std;

const int MAXN=1e3+5;

int n;
  
char a[MAXN][MAXN];

int dp[MAXN][MAXN];


int main()
{
  while(~scanf("%d",&n)&&n)
  {
    int ans=0;
    memset(a,‘\0‘,sizeof(a));
    memset(dp,0,sizeof(dp));
    for(int i=0;i=n)break;
          }
          if(i-x>dp[i-1][j+1])dp[i][j]=dp[i-1][j+1]+1;
          else dp[i][j]=i-x;
        }
        ans=max(dp[i][j],ans);
      }
    }
    printf("%d\n",ans);
  }
  return 0;
}

hdu 2859

原文：https://www.cnblogs.com/gugudesu/p/11159661.html