HDU 2859 Phalanx (dp)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2859

给你一个n*n的矩阵，问你最大的对称度是多少(左下右上为对称线)

dp[i][j]表示i行j列元素的最大对称度

每到一个元素的时候，往上边和右边扩展看字符最优的对称长度 与dp[i - 1][j - 1]进行比较取最优即可。

//#pragma comment(linker, "/STACK:102400000, 102400000")
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
typedef long long LL;
typedef pair <int, int> P;
const int N = 1e3 + 5;
int dp[N][N];
char str[N][N];

int main()
{
    int n;
    while(~scanf("%d", &n) && n) {
        for(int i = 1; i <= n; ++i) {
            scanf("%s", str[i] + 1);
        }
        memset(dp, 0, sizeof(dp));
        int res = 1;
        for(int i = 1; i <= n; ++i) {
            for(int j = n; j >= 1; --j) {
                int len = 1;
                while(str[i - len][j] == str[i][j + len] && i - len > 0 && j + len <= n) {
                    ++len;
                }
                dp[i][j] = max(1, min(dp[i - 1][j + 1], len - 1) + 1);
                res = max(res, dp[i][j]);
            }
        }
        printf("%d
", res);
    }
    return 0;
}