没网站域名可以做备案吗,网站导航大全,哈尔滨快速建站专业定制,泉州网站制作设计1.DP22 最长回文子序列
1.题目 2.解析
这是一个区间dp问题#xff0c;我们让dp[i][j]表示在区间[i#xff0c;j]内的最长子序列长度#xff0c;如图#xff1a; 3.代码
public class LongestArr {//DP22 最长回文子序列public static void main(String[] args) {Scanner…1.DP22 最长回文子序列
1.题目 2.解析
这是一个区间dp问题我们让dp[i][j]表示在区间[ij]内的最长子序列长度如图 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]表示在区间ij内的最长子序列长度//dp[i][j]当arr[i]arr[j]时为dp[i1][j-1]2;//当arr[i]!arr[j]时因为arr[i]和arr[j]其一肯定//有一个不在子序列中所以dp[i][j]Math.max(dp[i1][j],dp[i][j-1]);int n arr.length;int[][] dp new int[n][n];//初始化当ij时为1ij时为0因为长度为负数不能算有字符串ij时要计算最后取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所以判断xx-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 x10;x1n;x1) {for(int y10;y1n;y1) {for(int x2x1;x2n;x2) {for(int y2y1;y2n;y2) {//这里写判断大小的一系列逻辑 }}}
我们要计算矩阵内部的和有两种方法一种是暴力解法用两层for循环来一个一个加起来但是这样时间复杂度就是On^2加上外部循环就是 On^6。所以我们用第二种方法前缀和如图 那么如何使用呢如图 最后比较最大值就行 3.代码 public static void main(String[] args) {Scanner in new Scanner(System.in);int nin.nextInt();//输入数据int[][] arrnew int[n][n];for(int i0;in;i) {for(int j0;jn;j) {arr[i][j]in.nextInt();}}//用二维dp计算前缀和//dp[i-1][j-1]表示00到ij的前缀和大小//初始化int[][] dpnew int[n1][n1];for(int i1;in;i) {for(int j1;jn;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 x10;x1n;x1) {for(int y10;y1n;y1) {for(int x2x1;x2n;x2) {for(int y2y1;y2n;y2) {int temdp[y21][x21]-dp[y21][x1]-dp[y1][x21]dp[y1][x1];if(maxtem) {maxtem;}}}}}System.out.print(max);}
