用微软雅黑做网站可以吗百度百度一下你就知道主页

用微软雅黑做网站可以吗,百度百度一下你就知道主页,企业网站颜色,阿凡达营销网站区间DP第1课#xff1a;通过一个案例深入浅出研究区间DP 一、什么是区间DP 区间动态规划是动态规划的一种特殊形式#xff0c;用于解决涉及连续区间的最优化问题。它通过将问题分解为相互重叠的连续子区间#xff0c;并逐步合并这些子区间来解决整个问题。 核心特征 问题…区间DP第1课通过一个案例深入浅出研究区间DP一、什么是区间DP区间动态规划是动态规划的一种特殊形式用于解决涉及连续区间的最优化问题。它通过将问题分解为相互重叠的连续子区间并逐步合并这些子区间来解决整个问题。核心特征问题涉及序列或区间最优解可以通过合并相邻区间得到通常用二维数组dp[i][j]表示区间[i, j]的最优解二、基本思想与模板1. 状态定义// dp[i][j] 表示区间 [i, j] 上的最优解intdp[n][n];2. 通用解法框架// 1. 初始化长度为1的区间for(inti0;in;i){dp[i][i]初始值;}// 2. 按区间长度从小到大递推for(intlen2;lenn;len){// 区间长度for(inti0;ilen-1n;i){// 区间起点intjilen-1;// 区间终点// 3. 初始化当前区间根据问题决定初始值dp[i][j]INF 或0;// 4. 枚举分割点将区间分成两部分for(intki;kj;k){// 状态转移dp[i][j]min/max(dp[i][j],dp[i][k]dp[k1][j]合并代价);}}}三、常见问题类型与状态定义问题类型状态定义转移方程特点合并类问题dp[i][j]: 合并[i,j]的最小代价dp[i][j] min(dp[i][k]dp[k1][j]cost)匹配类问题dp[i][j]: [i,j]的最大匹配数考虑两端匹配和分割点回文类问题dp[i][j]: [i,j]是否为回文两端字符相等且内部是回文删除/插入类dp[i][j]: 使[i,j]合法的最少操作考虑删除、插入、替换操作本次课的研究案例题目描述设有N ( N ≤ 300 ) N(N \le 300)N(N≤300)堆石子排成一排其编号为1 , 2 , 3 , ⋯ , N 1,2,3,\cdots,N1,2,3,⋯,N。每堆石子有一定的质量m i ( m i ≤ 1000 ) m_i\ (m_i \le 1000)mi​(mi​≤1000)。现在要将这N NN堆石子合并成为一堆。每次只能合并相邻的两堆合并的代价为这两堆石子的质量之和合并后与这两堆石子相邻的石子将和新堆相邻。合并时由于选择的顺序不同合并的总代价也不相同。试找出一种合理的方法使总的代价最小并输出最小代价。输入格式第一行一个整数N NN。第二行N NN个整数m i m_imi​。输出格式输出文件仅一个整数也就是最小代价。输入输出样例 1输入 14 2 5 3 1输出 122思路分析1. 问题建模目标将N堆相邻石子合并为一堆要求合并总代价最小限制每次只能合并相邻两堆合并代价为两堆质量之和输入石子数量n每堆石子质量数组a[]输出最小合并代价2. 核心算法区间动态规划状态定义dp[i][j]表示合并第i堆到第j堆石子的最小代价边界条件当ij时单堆石子dp[i][i] 0状态转移枚举区间[i,j]的分割点k:dp[i][j]min{dp[i][k]dp[k1][j]}sum(i,j)(i ≤ kj)其中sum(i,j)表示区间[i,j]石子总质量通过前缀和数组O(1)计算3. 前缀和sum数组预处理前缀和数组sum[i] a[1]a[2]...a[i]快速计算区间和sum[j] - sum[i-1]可快速得到区间[i,j]的总质量4. 算法流程预处理前缀和数组初始化DP边界条件枚举区间长度从2到n枚举区间起点枚举区间分割点根据状态转移方程更新DP表5. 复杂度分析时间复杂度O(n³) → 三重循环n≤300时可接受空间复杂度O(n²) → DP表存储AC代码#includebits/stdc.husingnamespacestd;intn,a[310],sum[310];// a[]存储每堆石子质量sum[]为前缀和数组intdp[310][310];// dp[i][j]表示合并区间[i,j]的最小代价intmain(){cinn;// 读取数据并计算前缀和for(inti1;in;i){cina[i];sum[i]sum[i-1]a[i];// sum[i]表示前i堆石子的总质量}// 初始化DP数组为无穷大表示未计算状态memset(dp,0x3f,sizeof(dp));// 单个石子堆无需合并代价为0for(inti1;in;i){dp[i][i]0;}// 区间DP核心算法for(intlen2;lenn;len){// 枚举区间长度for(inti1;in1-len;i){// 枚举区间起点intjilen-1;// 计算区间终点for(intki;kj;k){// 枚举分割点// 状态转移方程合并[i,k]和[k1,j]的代价 当前合并的总质量dp[i][j]min(dp[i][j],dp[i][k]dp[k1][j]sum[j]-sum[i-1]);}}}coutdp[1][n]endl;// 输出合并全部石子的最小代价return0;}总结区间DP是信奥赛中非常重要且常见的题型掌握其核心思想小区间合并成大区间是关键。解题步骤通常是识别问题是否具有区间性质定义dp[i][j]状态确定状态转移方程如何通过分割点合并小区间确定遍历顺序和初始化考虑优化四边形不等式、前缀和等完整系列资料请查看专栏《csp信奥赛C动态规划》https://blog.csdn.net/weixin_66461496/category_13096895.html各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}一、CSP信奥赛C通关学习视频课C语法基础C语法进阶C算法C数据结构CSP信奥赛数学CSP信奥赛STL二、CSP信奥赛C竞赛拿奖视频课信奥赛csp-j初赛高频考点解析CSP信奥赛C复赛集训课12大高频考点专题集训三、考级、竞赛刷题题单及题解GESP C考级真题题解CSP信奥赛C初赛及复赛高频考点真题解析CSP信奥赛C一等奖通关刷题题单及题解详细内容1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转3、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转2025 csp-j 复赛真题及答案解析最新更新2025 csp-x(山东) 复赛真题及答案解析最新更新2025 csp-x(河南) 复赛真题及答案解析最新更新2025 csp-x(辽宁) 复赛真题及答案解析最新更新2025 csp-x(江西) 复赛真题及答案解析最新更新2025 csp-x(广西) 复赛真题及答案解析最新更新2020 ~ 2024 csp 复赛真题题单及题解2019 ~ 2022 csp-j 初赛高频考点真题分类解析2021 ~ 2024 csp-s 初赛高频考点解析2023 ~ 2024 csp-x (山东)初赛真题及答案解析2024 csp-j 初赛真题及答案解析2025 csp-j 初赛真题及答案解析最新更新2025 csp-s 初赛真题及答案解析最新更新2025 csp-x (山东)初赛真题及答案解析(最新更新)2025 csp-x (江西)初赛真题及答案解析(最新更新)2025 csp-x (辽宁)初赛真题及答案解析(最新更新)CSP信奥赛C一等奖通关刷题题单及题解持续更新https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转129 道刷题练习和详细题解涉及模拟算法、数学思维、二分算法、 前缀和、差分、深搜、广搜、DP专题、 树和图4、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}