笔试强训未触及题目（个人向）

1.DP22 最长回文子序列

1.题目

2.解析

这是一个区间dp问题，我们让dp[i][j]表示在区间[i，j]内的最长子序列长度，如图：

3.代码

public class LongestArr {//DP22 最长回文子序列
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        char[] arr = in.next().toCharArray();
        //让dp[i][j]表示在区间i，j内的最长子序列长度
        //dp[i][j]=当arr[i]==arr[j]时为dp[i+1][j-1]+2;
        //当arr[i]!=arr[j]时因为arr[i]和arr[j]其一肯定
        //有一个不在子序列中，所以dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
        int n = arr.length;
        int[][] dp = new int[n][n];
        //初始化，当i=j时为1，i>j时为0（因为长度为负数不能算有字符串，i<j时要计算，最后取dp[0][n-1]）
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (j == i) {
                    dp[i][j] = 1;
                } else {
                    if (arr[i] == arr[j]) {
                        dp[i][j] = dp[i + 1][j - 1] + 2;
                    } else {
                        dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                    }
                }
            }
        }
        System.out.print(dp[0][n - 1]);
    }
}

2.数组变换

1.题目

2.解析

那么综上所述我们只要知道最大的数是否能和其他数匹配就行，但是问题来了，怎么知道它们是否匹配呢。我们可以先让最大数除以另一个想要与之匹配的数，若除不尽，则不能匹配，若除尽，则判断商是否为2的n次方。这里除尽除不尽用%小数来表示。那怎么判断是否为2的n次方呢，这里有三种方式，一种是暴力求法，让这个数无限/2，%2即可，第二种是lowbit算法，判断x-(x&-x)是否为0，第三种就是之前做过的判断1的位数的位运算方法，因为我们只需要判断是否只有1位1，所以，判断x&（x-1）是否为0即可。下文采用的是lowbit算法。

3.代码

public class demo2 {//数组变换
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        //取最大的数和其余的数做比较，看这个数能否变成这个最大的数
        //输入时判断最大数
        int n = in.nextInt();
        int max = 0;
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            int tem = in.nextInt();
            if (i == 0) {
                max = tem;
            } else max = Math.max(tem, max);
            arr[i] = tem;
        }
        for (int i = 0; i < n; i++) {
            //判断能否变为最大的数
            if (max % arr[i] == 0) {
                int s = max / arr[i];
                if (s - (s & -s) != 0) {
                    System.out.print("NO");
                    return;
                }

            } else {
                System.out.print("NO");
                return;
            }
        }
        System.out.print("YES");
    }
}

3.DP10 最大子矩阵

1.题目

2.解析

在判断矩阵最大大小之前，我们肯定要枚举所有矩阵，如图：

for(int x1=0;x1<n;x1++) {
            for(int y1=0;y1<n;y1++) {
                for(int x2=x1;x2<n;x2++) {
                    for(int y2=y1;y2<n;y2++) {
                        //这里写判断大小的一系列逻辑                    
                }
            }
        }

我们要计算矩阵内部的和，有两种方法，一种是暴力解法，用两层for循环来一个一个加起来，但是这样时间复杂度就是O（n^2）加上外部循环就是 O（n^6）。所以我们用第二种方法，前缀和如图：

那么如何使用呢？如图：

最后比较最大值就行

3.代码

 public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        //输入数据
        int[][] arr=new int[n][n];
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                arr[i][j]=in.nextInt();
            }
        }
        //用二维dp计算前缀和
        //dp[i-1][j-1]表示（0，0）到（i，j）的前缀和大小
        //初始化
        int[][] dp=new int[n+1][n+1];
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=n;j++) {
                dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]
                        +arr[i-1][j-1];
            }
        }
        //枚举每一块矩阵
        int max=-0x3f3f3f3f;
        for(int x1=0;x1<n;x1++) {
            for(int y1=0;y1<n;y1++) {
                for(int x2=x1;x2<n;x2++) {
                    for(int y2=y1;y2<n;y2++) {
                        int tem=dp[y2+1][x2+1]-dp[y2+1][x1]-
                                dp[y1][x2+1]+dp[y1][x1];
                        if(max<tem) {
                            max=tem;
                        }
                    }
                }
            }
        }
        System.out.print(max);

    }