Q - Phalanx HDU - 2859——基础dp-最大对称子矩阵

超、凢脫俗 2022-06-10 04:11 147阅读 0赞

Think:  
1知识点：基础dp-最大对称子矩阵  
2题意：给定一个矩阵，寻找一个最大对称子矩阵，当前题目最大对称子矩阵定义可理解为沿当前子矩阵的次对角线元素对称  
3思考：确定动态转移方程的过程可以抽象成根据题意条件将一个大问题不断缩小一直缩小到可以解决的小问题

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    char st[1014][1014];
    int dp[1014][1014];
    
    int main(){
        int n, i, j, ans;
        while(scanf("%d", &n) && n){
            for(i = 0; i < n; i++)
                scanf("%s", st[i]);
            ans = 0;
            for(i = 0; i < n; i++){
                for(j = 0; j < n; j++){
                    if(i == 0 || j == n-1)
                        dp[i][j] = 1;
                    else {
                        int t1 = i, t2 = j;/*求当前元素行到最上方行所确定的局部列和当前元素列到最右方列所确定的局部行的最大对称长度*/
                        while(t1 >= 0 && t2 < n){
                            if(st[t1][j] == st[i][t2]){
                                t1--, t2++;
                            }
                            else
                                break;
                        }
                        int t = i - t1;
                        if(t > dp[i-1][j+1]+1)/*判断右上角矩阵是否为对称矩阵*/
                            dp[i][j] = dp[i-1][j+1] + 1;/*若右上角矩阵不是对称矩阵*/
                        else
                            dp[i][j] = t;/*若右上角矩阵为对称矩阵*/
                    }
                    ans = max(ans, dp[i][j]);
                }
            }
            printf("%d\n", ans);
        }
        return 0;
    }

[vjudge]: https://vjudge.net/contest/163018#problem/Q