关于#c++#的问题，请各位专家解答！

Question

这两题我不会？？
给朕解决了他！！
帮帮我！！
——20240409

Answer 1

晚上好🌙🌙🌙
本答案参考ChatGPT-3.5

问题1：如何求一个矩阵中不重叠的3x3子矩阵的最大元素和？

解决方案：

1. 遍历整个矩阵，以每个元素为起点，在其周围3x3的矩形区域内枚举所有可能的3x3子矩阵，计算它们的总和并更新最大值；

2. 为了避免重复计算，可以使用前缀和预处理矩阵a，这样在计算子矩阵的和时就可以直接利用前缀和相减的方式来求出子矩阵的和。

代码实现：

假设前缀和数组为pre，左上角为(i,j)的子矩阵和为：pre[i+2][j+2] - pre[i-1][j+2] - pre[i+2][j-1] + pre[i-1][j-1]。

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 12;
int n, a[N][N], sum[N][N], res;

void dfs(int cnt)  // cnt表示当前需要填入几个3x3子矩阵
{
    if (cnt <= 0)  // 若当前没有子矩阵能够放入，则更新答案
    {
        int s = 0;
        for (int i = 2; i <= n - 1; i++)  // 枚举所有3x3子矩阵
            for (int j = 2; j <= n - 1; j++)
                s = max(s, sum[i][j] - sum[i-3][j] - sum[i][j-3] + sum[i-3][j-3]);
        res = max(res, s);  // 更新最大值
        return;
    }

    for (int i = 0; i <= n - 3; i++)  // 枚举所有可行的3x3子矩阵位置（左上角）
        for (int j = 0; j <= n - 3; j++)
        {
            bool flag = true;  // 判断该子矩阵是否可以放入
            for (int k = i; k < i + 3; k++)
                for (int l = j; l < j + 3; l++)
                    if (sum[k][l] != cnt)  // 若该格子已被子矩阵覆盖，则不能再次放入
                    {
                        flag = false;
                        k = i + 3, l = j + 3;
                    }
            if (flag)  // 若该子矩阵可以放入，更新sum数组、填入"1"表示已被覆盖，并进行下一次递归
            {
                for (int k = i; k < i + 3; k++)
                    for (int l = j; l < j + 3; l++)
                        sum[k][l] = cnt + 1;
                dfs(cnt - 1);
                for (int k = i; k < i + 3; k++)
                    for (int l = j; l < j + 3; l++)
                        sum[k][l] = cnt;  // 回溯
            }
        }
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
        {
            cin >> a[i][j];
            sum[i][j] = a[i][j] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];  // 生成前缀和数组
        }

    dfs(4);  // 最多只能放4个3x3子矩阵
    cout << res << endl;

    return 0;
}

问题2：给定一个字符串S，求它的最长回文子序列的长度。

解决方案：

1. 对于一个字符串S，它的最长回文子序列长度可以转化为该字符串与它的逆序字符串的最长公共子序列长度，例如S="abccbda"则它的最长回文子序列为"abcba"，而其逆序字符串为"adbccb"，它们的最长公共子序列为"abcb"，其长度为4，即S的最长回文子序列的长度为4。

2. 对S的逆序字符串S'进行最长公共子序列LCS的求解，得到LCS字符串T，即S和S'的最长公共子序列字符串。由于T是S的子序列，因此可以采用动态规划DP的方式求解，设dp[i][j]为S前i个字符与S'前j个字符的LCS长度，则最终的答案为dp[len][len]。

代码实现：

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

const int N = 1010;
int dp[N][N];

int main()
{
    int len;
    string s;
    cin >> len >> s;

    string s_rev = s;
    reverse(s_rev.begin(), s_rev.end());  // 反转字符串获得逆序字符串
    for (int i = 1; i <= len; i++)
        for (int j = 1; j <= len; j++)
            if (s[i-1] == s_rev[j-1]) dp[i][j] = dp[i-1][j-1] + 1;  // 相等的情况
            else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);  // 不相等的情况，取左上方或上方的较大值
    cout << dp[len][len] << endl;

    return 0;
}