如何用flashfxp上传网站php开源公司网站

当前位置： 首页 > news >正文

如何用flashfxp上传网站,php开源公司网站,wordpress本地音乐,用网站ip做代理下将以括号序列、组合数问题超级吧难的题为例子讲解动态规划 别忘了请点个赞收藏关注支持一下博主喵#xff01;#xff01;#xff01;! ! ! ! #xff01; 关注博主#xff0c;更多蓝桥杯nice题目静待更新:) 动态规划 一、数字三角形
【问题描述】 上图给出了… 下将以括号序列、组合数问题超级吧难的题为例子讲解动态规划  别忘了请点个赞收藏关注支持一下博主喵!  !  !  ! 
关注博主更多蓝桥杯nice题目静待更新:) 动态规划 一、数字三角形  【问题描述】 上图给出了一个数字三角形。从三角形的顶部到底部有很多条路径。对于每条路径 把路径上面的数加起来可以得到一个和你的任务就是找到最大的和。 路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右边的那个 数。此外向左下走的次数与向右下走的次数相差不能超过1。   【输入格式】 输入的第一行包含一个整数N(1⩽N⩽100)表示三角形的行数。  下面的N行给出数字三角形。数字三角形上的数都是0至100之间的整数。 【输出格式】 输出一个整数表示答案。 【样例输入】 【样例输出】 27 解析  本题是十分经典的动态规划题。 为了方便存储与操作可以将题目描述中的等腰三角形转换为直角三角形如下图所示。 将其转换为直角三角形后就可以用一个二维数组a[][]来存储它。这样三角形第i行 的第j 个数字就可以通过a[i][j] 来表示。同时原来向左下走就变为了向下走本题下文解析所说的“向下走”即为“向左下走”向右下走还是向右下走。 在处理完样例输入后我们来尝试对题目进行求解。 由于“向左下走的次数与向右下走的次数相差不能超过1”这个限制条件看上去比较复杂所以我们可将该题分解为两个子问题: 第一个子问题是不考虑限制条件只解决如何走的问题第二个子问题是加上这个限制条件找到走到底部的最大路径和从而完整解答出本题。对于每个子问题都分别用DFS和动态规划两种方式来解题,大家可进一步体验这两种方式的特点。  解决子问题1DFS模式 题目要求我们从三角形的顶部开始走而顶部只有一个数字a[1][1]所以所走路径的起点一定是a[1][1]。 由于我们每一步只能向下走或者向右下走因此a[1][1]的下一步只有以下两种可能。 1走向a[2][1]。 2走向a[2][2]。 具体要走向哪个呢?我们并不好确定。 我们能得知的是如果设dfs(i,j) 表示从 a[i][j] 走到底部的最大路径和那么我们一定会走向max(dfs(2,1),dfs(2,2)) 所对应的路径即从 a[1][1] 走到底部的最大路径和 在该式子中dfs(1,1) 是我们要求解的a[1][1] 是已知的dfs(2,1)、dfs(2,2) 是未知的。 显然只要存在未知数就无法求解dfs(1,1)的值。因此必须先求解dfs(2,1) 和dfs(2,2)。 但要怎么求解它们呢? 我们以求解dfs(i,j) 为例。 当a[i]j 不在底部时每一步只能向下走或者向右下走因此a[i][j] 的下一步只有两种可能。 1走向a[i1][j]。 2走向a[i1][j 1]。 当a[i]j 在底部时我们将无法再走任何一步。 由此可得 : 参考代码如下 【时间复杂度为 O()】  #include bits/stdc.h using namespace std;const int N 1e2 10; int n, a[N][N];int dfs(int i, int j) {if (i n) return a[i][j]; // 走到底部无法再走了直接返回return max(dfs(i 1, j), dfs(i 1, j 1)) a[i][j]; }signed main() {cin n;for (int i 1; i n; i) {for (int j 1; j i; j) {cin a[i][j];}}cout dfs(1, 1) \n;return 0; } 在上方代码中每次dfs都几乎调用了自己两次所以代码的时间复杂度约为O()。  如果一个三角形的行数为4则程序的递归过程将如下图所示。 显然O() 的时间复杂度是十分低效的无法帮助我们顺利解出本题。至于复杂度低效的原因从上图中不难发现是因为在递归的过程中做了过多重复的计算比如在上图中 dfs(3, 2) 就重复计算了一次。 那么我们要如何避免递归时的重复计算呢? 可以采用一个简单且高效的方法——记忆化即定义一个二维数组res[][]用res[i][j]保 存dfs(i,j) 的计算结果。当再次需要dfs(i,j) 的计算结果时直接返回res[i][j] 即可无须继续递归下去。 使用了记忆化的方法优化后最多只需进行约次递归。  参考代码如下 【时间复杂度为 O()】 #include bits/stdc.h using namespace std;const int N 1e2 10; int n, a[N][N], res[N][N];int dfs(int i, int j) {if (res[i][j]) return res[i][j]; // 如果 res[i][j] 不为 0说明已经计算过直接返回结果if (i n) return a[i][j]; // 到达底部返回当前值return res[i][j] max(dfs(i 1, j), dfs(i 1, j 1)) a[i][j]; // 计算并存储结果 }signed main() {cin n;for (int i 1; i n; i) {for (int j 1; j i; j) {cin a[i][j];}}cout dfs(1, 1) \n;return 0; } 解决子问题1动态规划模式 与DFS 不同的是动态规划通常是采用递推的方式从上到下来求解问题。 在本题中我们从三角形的顶部(1,1)走到三角形的某个位置(i,j)的方法颇多根据不同的走法所得到的路径和可能会有所差异。 由于本题需要求解的是从三角形顶部(1,1) 走到底部的最大路径和所以在不同方法带 来的不同路径和中我们只需要关注最大路径和即可。 于是我们可以定义一个数组dp[][]其中dp[i][j] 用以表示从三角形顶部(11) 走到(ij) 的所有路径和中的最大值。 当走到底部时所处的位置可能有(n,1)、(n,2)、…、(n,n)它们对应的最大路径和分 别为dp[n][1]、dp[n][2]、…、dp[n][n]。我们要的是这当中的最大路径和即 。 起初处于三角形的顶部(1,1)。因为从(1,1) 走到(1,1) 的方法仅有一种所以我们可 得dp[1][1] a[1][1]。 1从位置(i−1,j) 向下走一步。 2从位置(i−1,j−1) 向右下走一步。 无论我们选择哪种从(1,1) 到(i,j) 的路径与 (1,1) 到 (i−1,j) 或 (i−1,j−1) 的路径都只会有一步之差。所以两种方法到达(i,j)的最大路径和分别如下。 1dp[i−1][j]a[i][j]。 2dp[i−1][j −1]a[i][j]。 为了使到达位置(i,j) 的路径和最大我们需要从这两种方法中选择较大的一种即 这样我们便完成了dp方程的转移。        参考代码如下 【时间复杂度为 O()】   #include bits/stdc.h using namespace std;const int N 1e2 10; int n, a[N][N], dp[N][N];signed main() {cin n;for (int i 1; i n; i) {for (int j 1; j i; j) {cin a[i][j];}}dp[1][1] a[1][1];for (int i 2; i n; i) {for (int j 1; j i; j) {dp[i][j] max(dp[i - 1][j], dp[i - 1][j - 1]) a[i][j];}}int ans 0;for (int j 1; j n; j) {ans max(ans, dp[n][j]);}cout ans \n;return 0; } 提示 以上情况都是在不考虑“向左下走的次数与向右下走的次数相差不能超过1”这个限制 条件下分析的接下来我们来思考加上向左下走的次数与向右下走的次数相差不能超过1这个限制条件之后该如何处理即解决子问题2。 为了方便读者理解接下来我们分别用动态规划和DFS两种方法对本题进行讲解。 解决子问题2动态规划模式 我们可以采用最简单的方法从顶部向底部走的过程中额外添加一个状态——向下走 的次数即定义dp[i][j][k]表示从(1,1)走到(i,j)一共向下走了k次的最大和。 根据向下走和向右下走的次数相差不能超过1的条件那么从第1行到第n行一共要走 n−1步由此可得 •当n−1为奇数n为偶数时向下走的次数可以为 也可以为  1 •当n−1为偶数n为奇数时向下走的次数只能为 。 那么答案就可表示为 对于位置(i,j)它可以由位置 (i − 1,j) 向下走了一步得到也可以由位置(i−1,j−1) 向右下走了一步得到于是dp转移方程为  参考代码如下【时间复杂度为O()】  #include bits/stdc.h using namespace std;const int N 1e2 10; int n, a[N][N], dp[N][N][N];signed main() {memset(dp, -0x3f, sizeof(dp)); // 某些情况可能并不存在如 dp[2][1][0]走到位置 (2,1) 时共向下走了 0 次。为了防止这种情况被转移需初始化 dp 数组cin n;for (int i 1; i n; i) {for (int j 1; j i; j) {cin a[i][j];}}dp[1][1][0] a[1][1];for (int i 2; i n; i) {for (int j 1; j i; j) {for (int k 0; k (n - 1); k) {if (!k) {dp[i][j][k] dp[i - 1][j - 1][k] a[i][j];} else {dp[i][j][k] max(dp[i - 1][j - 1][k], dp[i - 1][j][k - 1]) a[i][j];}}}}int ma 0;if ((n - 1) 1) {for (int j 1; j n; j) {ma max(ma, max(dp[n][j][(n - 1) / 2], dp[n][j][(n - 1) / 2 1]));}} else {for (int j 1; j n; j) {ma max(ma, dp[n][j][(n - 1) / 2]);}}cout ma \n;return 0; } 虽说运用上述的方法已经可以完成本题了但我们其实不额外添加一个状态也可以解决。 由上可得以下结论。 •当n−1为奇数n为偶数时向下走的次数可以为 也可以为  1 •当n−1为偶数n为奇数时向下走的次数只能为 。 基于向下走的次数、向右下走的次数限制不难发现以下情况。 •当n−1为奇数n为偶数时无论中间的路线是什么样的最后的位置只有两种可能 ( n , 1   ) n , 1    1 )。 •当n为偶数时无论中间的路线是什么样的最后的位置只有一种可能 ( n , 1   )。 所以我们并不需要考虑从顶部走到底部时向下走的次数只需要保证最后的位置正确即可。 用dp[i][j]表示从(1,1)走到(i,j)的最大和并对其进行转移那么答案就可以表示为 参考代码如下【时间复杂度为O()】  #include bits/stdc.h using namespace std;const int N 1e2 10; int n, a[N][N], dp[N][N];signed main() {cin n;for (int i 1; i n; i) {for (int j 1; j i; j) {cin a[i][j];}}dp[1][1] a[1][1];for (int i 2; i n; i) {for (int j 1; j i; j) {dp[i][j] max(dp[i - 1][j - 1], dp[i - 1][j]) a[i][j];}}// 根据 n-1 的奇偶性输出在满足向下走的次数与向右下走的次数相差不能超过 1 的条件下可能会到达的位置对应的 dp 值if ((n - 1) 1) {cout max(dp[n][1 (n - 1) / 2], dp[n][1 (n - 1) / 2 1]) \n;} else {cout dp[n][1 (n - 1) / 2] \n;}return 0; } 解决子问题2DFS模式  DFS的处理方法和动态规划的类似有以下两种方法 1额外添加一个状态使得答案满足条件 2保证最后的位置正确使得答案满足条件。 下面给出第二种方法的参考代码。 参考代码如下 #include bits/stdc.h using namespace std;const int N 1e2 10; int n, a[N][N], res[N][N];int dfs(int i, int j) {if (res[i][j]) return res[i][j]; // 如果 res[i][j] 不为 0说明已经计算过直接返回结果if (i n) {if (n % 2 j n / 2 1) return a[i][j]; // n 为奇数且 j 为中间位置if (n % 2 0 (j n / 2 || j n / 2 1)) return a[i][j]; // n 为偶数且 j 为中间两个位置之一return -10000000; // 位置不正确时返回一个极大的负数}return res[i][j] max(dfs(i 1, j), dfs(i 1, j 1)) a[i][j]; // 计算并存储结果 }signed main() {cin n;for (int i 1; i n; i) {for (int j 1; j i; j) {cin a[i][j];}}cout dfs(1, 1) \n;return 0; } 二、砝码称重 【问题描述】 你有一架天平和N个砝码这N个砝码重量依次是W1,W2,…,WN。 请你计算一共可以称出多少种不同的重量。注意砝码可以放在天平两边。 【输入格式】 输入的第一行包含一个整数N。 第二行包含N个整数W1,W2,W3,…,WN。 【输出格式】 输出一个整数表示答案。 【样例输入】 【样例输出】 10 【样例说明】 【评测用例规模与规定】 对于50% 的评测用例1⩽ N ⩽15。 对于所有评测用例1⩽ N ⩽100N 个砝码总重不超过100000。 解析 本题是道有限制的选择问题、背包问题的变形题。 在本题中题目给定了1个天平及n个砝码每个砝码都有自己的重量。天平存在以下 3 种状态。 1平衡。 2向左倾斜。 3向右倾斜。 这3种状态分别可称出的重量 10忽略不计 2左侧的砝码重量−右侧的砝码重量 3右侧的砝码重量−左侧的砝码重量。 显然天平的状态只会受到两侧砝码的重量影响。对于每个砝码它都有以下3种处理方式。 1放在天平的左侧。 2放在天平的右侧。 3两侧都不放。 那么n个砝码就有3n种处理方式情况。 在50%的评测用例中1⩽n⩽15。当n15时31514348907数据规模为107 左右。 因此我们可以使用直接dfs“暴力”搜索出放置n个砝码的所有情况并统计这些情况能够称出的不同重量的个数。 1dfs“暴力”搜索 参考代码如下【时间复杂度为O()】 #include bits/stdc.h using namespace std;const int N 1e2 10, M 1e5 10; int n, ans, w[N], vis[M]; // vis[x] 1 表示可以称出重量 xvoid dfs(int i, int left, int right) {if (i n) {vis[max(left, right) - min(left, right)] 1;return;}// 将第 i 个砝码放置在左边dfs(i 1, left w[i], right);// 将第 i 个砝码放置在右边dfs(i 1, left, right w[i]);// 两边都不放dfs(i 1, left, right); }signed main() {cin n;for (int i 1; i n; i) {cin w[i];}dfs(1, 0, 0);for (int i 1; i M; i) {if (vis[i]) {ans;}}cout ans \n;return 0; } 可当 1 ⩽ n ⩽100 时还能用dfs搜索出所有情况吗?显然不行因为当n100时 会是个天文数字计算机在有限的时间内是不可能搜索出所有情况的。 那怎么办呢? 考虑用动态规划解决。  2动态规划【正解】 1. 设计状态数组 按照常规的步骤我们会设计一个状态数组dp[]其中dp[i]表示用前i个砝码所能称出 的不同重量的个数。 这么设计看似合理答案也可以用dp[n] 轻松表示但略加思考后不难发现其存在一个 致命问题即在状态转移的过程中无法处理相同的重量被重复计算的情况。 如何解决这个致命问题呢?我们只要将重量也设计在状态数组中即设计一个boolean类 型的二维数组dp[][]其中 dp[i][j] true 表示前 i 个砝码能通过天平称出重量 jdp[i][j] false 则表示前 i 个砝码不能通过天平称出重量j。 由于n个砝码的总重量不超过100000所以我们只要在求解完整个数组后枚举dp[n][1∼ 100000]统计其中值为 true 的元素个数即可得出 n 个砝码所能称出的不同重量的个数。 到这里貌似没有什么问题。那么接下来我们就来讨论一下如何求解dp[][]数组。

1. 初始状态 起初我们未在天平两侧放置任何砝码天平它会处于一种平衡的状态。我们可以认为 此时天平称的重量为0即dp[0][0]true。
2. 推导转移方程 事实上天平所称出的重量总是会由重的一侧减去轻的一侧即对于第i个砝码若我 们将其放入天平较重的一侧则它将使天平称出的重量增加wi若将该砝码放入天平较轻的 一侧则它将使天平称出的重量减少wi。例如在我们处理完前i−1个砝码后天平所称 出的重量为j那么在处理完第i个砝码后天平所能称出的重量将会根据对第i个砝码不 同的处理方式得到3种不同结果分别如下。 1jwi将第i 个砝码放在较重的一侧。 2j−wi将第i 个砝码放在较轻的一侧。 3j两侧都不放。 因此我们可推导出以下3种状态转移式 因此我们可推导出以下3种状态转移式 若将3个状态转移式整合成一个可得  完成状态转移式的推导。 值得注意的是在进行状态转移的过程中可能会出现 j w[i] 的情况 j - w[i] 0 。若不进行处理就会导致数组的越界进而导致答案错误。 因此我们可以为所有重量添加一个偏移量offset对于重量x用xoffset来表示它 如下图所示使得∀j−w[i]offset⩾0。 提示添加上offset 后dp[i][j] 的含义为前 i 个砝码能否通过天平称出重量 j−offset。 参考代码如下【时间复杂度为 O(n× n ∑ i1 wi)】 #include bits/stdc.h using namespace std;const int N 1e2 10, M 1e5 10, offset 1e5; int n, ans, w[N], dp[N][2 * M];signed main() {cin n;for (int i 1; i n; i) {cin w[i];}dp[0][0 offset] true;for (int i 1; i n; i) {for (int j 0; j M offset; j) {if (j - w[i] 0) dp[i][j] | dp[i - 1][j - w[i]];dp[i][j] | dp[i - 1][j w[i]] | dp[i - 1][j];}}for (int i 1 offset; i M offset; i) {if (dp[n][i]) ans;}cout ans \n;return 0; } 。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。 下将以括号序列、组合数问题超级吧难的题为例子讲解动态规划 别忘了请点个赞收藏关注支持一下博主喵!  !  !  ! 关注博主更多蓝桥杯nice题目静待更新:)