企业官网建设流程全解析

苏州网络科技公司建网站,上海轨道交通建设查询网站,现代网站制作,wordpress 添加meta区间DP第2课#xff1a;区间DP应用案例实践1 题目描述 约翰经常给产奶量高的奶牛发特殊津贴#xff0c;于是很快奶牛们拥有了大笔不知该怎么花的钱。为此#xff0c;约翰购置了 NNN#xff08;1≤N≤20001 \leq N \leq 20001≤N≤2000#xff09; 份美味的零食来卖给奶牛…区间DP第2课区间DP应用案例实践1题目描述约翰经常给产奶量高的奶牛发特殊津贴于是很快奶牛们拥有了大笔不知该怎么花的钱。为此约翰购置了N NN1 ≤ N ≤ 2000 1 \leq N \leq 20001≤N≤2000 份美味的零食来卖给奶牛们。每天约翰售出一份零食。当然约翰希望这些零食全部售出后能得到最大的收益这些零食有以下这些有趣的特性零食按照1 , … , N 1, \ldots, N1,…,N编号它们被排成一列放在一个很长的盒子里。盒子的两端都有开口约翰每天可以从盒子的任一端取出最外面的一个。与美酒与好吃的奶酪相似这些零食储存得越久就越好吃。当然这样约翰就可以把它们卖出更高的价钱。每份零食的初始价值不一定相同。约翰进货时第i份零食的初始价值为V i V_iVi​1 ≤ V ≤ 1000 1 \leq V \leq 10001≤V≤1000。第i ii份零食如果在被买进后的第a aa天出售则它的售价是V i × a V_i \times aVi​×a。V i V_iVi​是从盒子顶端往下的第i ii份零食的初始价值。约翰告诉了你所有零食的初始价值并希望你能帮他计算一下在这些零食全被卖出后他最多能得到多少钱。输入格式第一行一个正整数N NN。第二行N NN个正整数V 1 ∼ V N V_1 \sim V_NV1​∼VN​。输出格式一行一个整数表示答案。输入输出样例 1输入 15 1 3 1 5 2输出 143说明/提示样例的最优解是按1 → 5 → 2 → 3 → 4 1 \to 5 \to 2 \to 3 \to 41→5→2→3→4的顺序卖零食得到的钱数是1 × 1 2 × 2 3 × 3 4 × 1 5 × 5 43 1 \times 1 2 \times 2 3 \times 3 4 \times 1 5 \times 5 431×12×23×34×15×543。方法思路问题分析每次出售零食时可以选择从队列的头部或尾部取出因此这是一个典型的区间动态规划问题。我们需要计算每个子区间的最大收益并逐步合并这些结果来解决整个问题。动态规划状态定义定义dp[i][j]表示从第i个到第j个零食的区间内能获得的最大收益。状态转移方程对于每个区间[i, j]当前出售的天数为a n - (j - i)其中n是总天数。我们可以选择出售左端或右端的零食并取最大收益出售左端的收益为v[i] * a dp[i1][j]出售右端的收益为v[j] * a dp[i][j-1]因此状态转移方程为dp[i][j] max(v[i] * a dp[i1][j], v[j] * a dp[i][j-1])初始化当区间长度为1时直接计算该零食在第n天出售的价值。计算顺序按区间长度从小到大计算逐步合并子区间的结果。解决代码#includebits/stdc.hintv[2005];intdp[2005][2005];intmain(){intn;cinn;for(inti1;in;i){cinv[i];}// 初始化长度为1的区间for(inti1;in;i){dp[i][i]v[i]*n;}// 处理长度从2到n的区间for(intlen2;lenn;len){for(inti1;in-len1;i){intjilen-1;intan-(j-i);// 计算当前的天数dp[i][j]max(v[i]*adp[i1][j],v[j]*adp[i][j-1]);}}coutdp[1][n]endl;return0;}代码解释输入处理读取零食数量n和每个零食的价值v[i]。初始化对于每个长度为1的区间[i, i]其最大收益为当前零食在第n天的价值。动态规划计算按区间长度从小到大遍历计算每个区间的最大收益。对于每个区间[i, j]计算当前天数a并根据选择左端或右端的零食更新最大收益。输出结果最终结果存储在dp[1][n]中表示整个区间[1, n]的最大收益。完整系列资料请查看专栏《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;}