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

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);}