手机端网站建设要点,wordpress全部404,网站权重一直做不上去,上市的网站设计公司前言
前面讲的都是背包的基础问题#xff0c;这一节我们进行背包问题的实战#xff0c;题目来源于一位朋友的询问#xff0c;其实在这之前很少有题目是我自己独立做的#xff0c;我一般习惯于先看题解#xff0c;验证了题解提供的代码是正确的后#xff0c;再去研究题解…前言
前面讲的都是背包的基础问题这一节我们进行背包问题的实战题目来源于一位朋友的询问其实在这之前很少有题目是我自己独立做的我一般习惯于先看题解验证了题解提供的代码是正确的后再去研究题解这就给我自己养成了一种依赖的习惯。我害怕自己去挑战没有答案的问题朋友问的这道题来源于一个小众网站因此没有题解出于试一试的态度我也算比较轻松的做出来了让我十分有满足感十分感谢他。但是他好久之前问我的一道题我现在还没有回他sorry。话不多说看题目吧。
数的分解
题目描述 把 A 分解成 B 个各不相同的正整数之和并且要求每个正整数都不包含数字 2和4一共有多少种不同的分解方法注意交换几个整数的顺序被视为同一种方法例如 1000100118 和 1001100018被视为同一种。 输入描述 第一行包一个整数 T表示测试数据的规模。接下来 T 行每行 2 个整数A,B。 输出描述 对每个输入输出一个整数表示答案。 输入数据 2 10 2 2019 3 输出数据 2 40785 评测用例规模与约定 对于所有评测用例1≤T≤101≤A≤25001≤B≤10。 这道题目类似于蓝桥杯的一道真题那道真题是分解数字2019可以去看一下数的分解。因为那个题目只分解一个数字所以采用dfs甚至for循环枚举都可以过。但是这道题目是分解好几个数字而且分解后数字的个数也不是固定的如果用dfs会超时。 那么试着考虑一下动态规划因为无法为它划分为区间状压期望树形所以只能是普通的dp那就用普通的dp的思考顺序进行思考。 定义dp数组 第一步缩小规模。 考虑分解成B个整数那么我用B当作数据规模。 第二步限制。 需要记录当前B个数字之和是多少。除了这一个限制还有什么限制呢选出来的数字不能包含2或4这一个限制好考虑只需要在选择的时候检查一遍就可以了。还有呢还有需要保证选择的方案不会重复这种限制最常见的是用abc来约束即后一个一定比前一个大这样相当于规定了选择的顺序但是如果是这样的话我需要知道前一个选择的是啥这个时候就需要记录。其它限制应该没有了。 第三步写出dp数组。 dp[i][j][k]表示当前选择了i个数字所选数字之和为j且最后一个选择的数字是k时的。这样要求啥求方案数啊一般求啥表示啥也有特殊情况所以‘’表示的是方案数。 第四步推状态转移方程。 dp[i][j][k]应该从哪里转移过来呢必然是从前i-1个数字的状态转移这个状态还应该考虑此时j和k的情况当前可以选择的数字必然是比j小比k大,假设当前选择的数字是p则 k p j kpj kpj。所以 d p [ i ] [ j ] [ p ] d p [ i − 1 ] [ j − p ] [ k ] dp[i][j][p] dp[i-1][j-p][k] dp[i][j][p]dp[i−1][j−p][k] 综上状态转移方程如下 d p [ i ] [ j ] [ p ] d p [ i − 1 ] [ j − p ] [ k ] dp[i][j][p] dp[i-1][j-p][k] dp[i][j][p]dp[i−1][j−p][k] 考虑写代码了 第一步确定好遍历顺序。 对于背包问题一般第一个for遍历规模第二个for遍历限制。但是我们的限制有两个所以加上规模一共三层嵌套的for循环。 第二步确定好转移位置。 对于当前可以选择的数字只要比k大我都可以尝试在这一步选择所以需要一个for循环遍历此时转移的数字。综上一共4层嵌套的for循环。那么代码如下 int dp[][][] new int[k1][n1][n1];//n表示要分解的数字k表示分解后的数字个数// TODO Auto-generated method stubfor(int i 1;i n;i) dp[1][i][i] 1;for(int i 1;i k;i) {//10 遍历规模for(int j 1;j n;j) {//2500 遍历限制 for(int q 1;q j;q) {//if(check(q)) continue;//检查是否包含了2或4for(int p q1;p j;p) {if(check(p)) continue;dp[i][j][p] dp[i-1][j-p][q]; }}}}可以算一下上述思路的时间复杂度是 O ( k ∗ n ∗ n ∗ n ) 10 ∗ 2500 ∗ 2500 ∗ 2500 1 e 8 O(k*n*n*n)10*2500*2500*25001e8 O(k∗n∗n∗n)10∗2500∗2500∗25001e8会超时。那么在写上述思路的过程中你有没有发现一个问题。对于n范围内的数字我只有可能会选择一次选择k个数字并且数字之和恰好等于n这像不像二维01背包问题没错就是按照刚刚所想重新思考dp数组。 定义dp数组 第一步缩小规模。 对于n范围内的数字我只有可能会选择一次小于n的所有数字都可以看作是一个物品一共有n个物品。 第二步限制。 限制1选出来的数字不能包含2或4这一个限制好考虑只需要在选择的时候检查一遍就可以了不需要新的维度。 限制2选出来的数字个数不能超过B需要一个维度来限制。 限制3选出来的数字之和不能超过n需要一个维度来限制。 第三步写出dp数组。 dp[i][j][k]表示当前选择了i个数字所选数字之和为k所选数字个数为j时的方案数。 第四步推状态转移方程。 dp[i][j][k]应该从哪里转移过来呢必然是从前i-1个数字的状态转移如果第i个数字不选则 dp[i][j][k] dp[i-1][j][k]如果选择第i个数字则 dp[i][j][k] dp[i-1][j-1][k-i] 综上状态转移方程如下 i f ( k i ) if(ki) if(ki) d p [ i ] [ j ] [ p ] d p [ i − 1 ] [ j ] [ k ] d p [ i − 1 ] [ j − 1 ] [ k − i ] dp[i][j][p] dp[i-1][j][k]dp[i-1][j-1][k-i] dp[i][j][p]dp[i−1][j][k]dp[i−1][j−1][k−i] e l s e else else d p [ i ] [ j ] [ p ] d p [ i − 1 ] [ j ] [ k ] dp[i][j][p] dp[i-1][j][k] dp[i][j][p]dp[i−1][j][k] 考虑写代码了 第一步确定好遍历顺序。 对于背包问题一般第一个for遍历规模第二个for遍历限制。但是我们的限制有两个所以加上规模一共三层嵌套的for循环。 第二步确定好转移位置。 当前第i个数字进行转移所以不需要额外的for循环代码如下
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;
public class Main{static int n,k,ans0;//检查是不是带有2 或 4static Boolean check(int parm) {while(parm0) {int tparm%10;if(t2 || t4) return true;parm/10;}return false;}
public static void main(String[] args) {
// f();Scanner scanner new Scanner(System.in);int t scanner.nextInt();long dp[][][] new long[25001][101][25001];//当前考虑的物品当前选择的物品个数当前选择的物品的重量当前物品选还是没选while(t-- 0) {nscanner.nextInt();k scanner.nextInt();int sum0;//从2500个物品里选10个物品且价值恰好为n dp[0][0][0]1;for(int i 1;i n;i) {dp[i][1][i] 1; dp[i][0][0] 1;
// dp[1][0][0][0] 1;}for(int i 1;i n;i) {//for(int j 1;j k;j) {//for(int q 1;q n;q) {//if(check(i)) {dp[i][j][q] dp[i-1][j][q];}else {if(q i)dp[i][j][q] dp[i-1][j-1][q-i]dp[i-1][j][q];elsedp[i][j][q] dp[i-1][j][q];}
// System.out.println(dp[i][j][q] i j q);}}}long ans 0;ans dp[n][k][n]; System.out.println(ans);}
}
}此时的时间复杂度是 O ( B ∗ A ∗ A ) 10 ∗ 2500 ∗ 2500 62500000 1 e 8 O(B*A*A)10*2500*2500625000001e8 O(B∗A∗A)10∗2500∗2500625000001e8貌似可以但是别忘了还有T所以时间复杂度应该是 O ( B ∗ A ∗ A ∗ T ) 10 ∗ 2500 ∗ 2500 ∗ 10 62500000 1 e 8 O(B*A*A*T)10*2500*2500*10625000001e8 O(B∗A∗A∗T)10∗2500∗2500∗10625000001e8但是我们可以看到当n2500t1时是不超时的而对于其它的n2500和k10其实可以直接用dp[n][k][n]来表示所以我们只需要预处理出n2500和k10的情况然后针对其它样例直接输出就可以了。 超时的问题解决了还有一个问题不太常遇到的问题空间超限因为我们设的数组是三维的空间大小将近1e9了。这里可以考虑用滚动dp来节省空间滚动dp在背包问题一中进行过讲解修改后的代码如下
import java.util.Arrays;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;public class Main{static int n,k,ans0;//检查是不是带有2 或 4static Boolean check(int parm) {while(parm0) {int tparm%10;if(t2 || t4) return true;parm/10;}return false;}
public static void main(String[] args) {
// f();Scanner scanner new Scanner(System.in);int t scanner.nextInt();long dp[][][] new long[2][101][25001];//当前考虑的物品当前选择的物品个数当前选择的物品的重量当前物品选还是没选dp[0][0][0] 1;dp[1][1][1] 1;dp[1][0][0] 1;n 2500;k 10;for(int i 1;i n;i) {//for(int j 1;j k;j) {//for(int q 1;q n;q) {// if(check(i)) {dp[i1][j][q] dp[(i-1)1][j][q];}else {if(q i)dp[i1][j][q] dp[(i-1)1][j-1][q-i]dp[(i-1)1][j][q];elsedp[i1][j][q] dp[(i-1)1][j][q];}
// System.out.println(dp[i][j][q] i j q);}}}while(t-- 0) {nscanner.nextInt();k scanner.nextInt();long ans 0;ans dp[n1][k][n]; System.out.println(ans);}
}
}这个网站的题目应该是对蓝桥杯题目进行了改编不得不说改编的质量还是挺高的再来另一个类似的题目
数的分解2
题目描述 将 N 拆分成 M 个正整数之和总共有多少种拆分方法注意交换顺序视为不同的方法例如 2025 1000 1025 和 2025 1025 1000 就视为不同的方法。 输入描述 第一行包一个整数 T表示测试数据的规模。接下来 T 行每行 2 个整数,N,M。 输出描述 对每个输入输出一个整数表示答案。由于答案可能会很大请输出答案除以 1097 的结果。 输入数据 2 40 5 1988 2 输出数据 82251 1987 评测用例规模与约定 对于所有评测用例1≤T≤101≤N≤25001≤M≤10。 这道题和上一道题有什么区别呢除了没有不能选包含2和4的数字的约数之外还规定了不同的顺序视为不同的方案这样就不是01背包了。因为对于01背包而言1011和1110是一种方案。还是先按照dp的步骤考虑一下。 定义dp数组 第一步缩小规模。 考虑分解成B个整数那么我用B当作数据规模。 第二步限制。 需要记录当前B个数字之和是多少。 第三步写出dp数组。 dp[i][j]表示当前选择了i个数字所选数字之和为j时的方案数。 第四步推状态转移方程。 dp[i][j]应该从哪里转移过来呢必然是从前i-1个数字的状态转移这个状态还应该考虑此时j的情况当前可以选择的数字必然是比j小,假设当前选择的数字是p则 p j pj pj。所以 d p [ i ] [ j ] d p [ i − 1 ] [ j − p ] dp[i][j] dp[i-1][j-p] dp[i][j]dp[i−1][j−p] 综上状态转移方程如下 d p [ i ] [ j ] [ p ] d p [ i − 1 ] [ j − p ] dp[i][j][p] dp[i-1][j-p] dp[i][j][p]dp[i−1][j−p] 考虑写代码了 第一步确定好遍历顺序。 对于背包问题一般第一个for遍历规模第二个for遍历限制。 第二步确定好转移位置。 对于当前可以选择的数字只要比j小我都可以尝试在这一步选择所以需要一个for循环遍历此时转移的数字。综上一共3层嵌套的for循环。那么代码如下
import java.util.Arrays;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;public class Main{static int n,k,ans0;
public static void main(String[] args) {Scanner scanner new Scanner(System.in);int t scanner.nextInt();n 2500;k 10;int mod (int) (1e97);int dp[][] new int[k1][n1];// TODO Auto-generated method stubfor(int i 1;i n;i) dp[1][i] 1;for(int i 1;i k;i) {//10 遍历规模for(int j 1;j n;j) {//2500 遍历限制 for(int q 1;q j;q) {//dp[i][j] dp[i-1][j-q]; dp[i][j] % mod;}}}while(t-- 0) {nscanner.nextInt();k scanner.nextInt();long ans 0;ans dp[k][n]; System.out.println(ans);}
}该思路的时间复杂度是 O ( N ∗ M ∗ N ) 2500 ∗ 2500 ∗ 10 1 e 8 O(N*M*N)2500*2500*101e8 O(N∗M∗N)2500∗2500∗101e8可以通过本题。 可以看见同一个思路因为限制的降低dp数组维数降低时间复杂度就降低了。
