网站基础建设和维护,鲤城网站建设推广服务公司,花房姑娘在线影院,南京网站制作多少钱竞赛总览
CSDN 编程竞赛三十四期#xff1a;比赛详情 (csdn.net)
本期的题目和第三十一期竞赛的题目竟然高度重合#xff0c;真不知道该写点什么了。
不过#xff0c;上次那道测试数据有bug的题已经修复了#xff0c;答题过程挺顺利的#xff0c;没有遇到新的问题。
竞…竞赛总览
CSDN 编程竞赛三十四期比赛详情 (csdn.net)
本期的题目和第三十一期竞赛的题目竟然高度重合真不知道该写点什么了。
不过上次那道测试数据有bug的题已经修复了答题过程挺顺利的没有遇到新的问题。
竞赛题解
题目1、最优利润值
你在读的经营课程上老师布置了一道作业。在一家公司的日常运营中会对一些商品的价格走势根据一些经验和数据进行预估并据此进行决策。例如假设某商品每天的价格都有可能变动我们要做的就是低买高卖获得最高利润。比如假设我们预估该商品接下来七天内的价格走势如下4 1 2 3 6 4 8那我们采取的最佳策略是在价格1块钱的时候买入在价格8块钱的时候卖出。为了简化整个过程我们限定在此周期内只能有一次买入一次卖出且商品在没有购入前是无法卖出的即该商品不是期货而是现货。现要求你用程序来实现自动决策。输入一定天数的商品预估价格自动计算出最优利润值。例如上面的例子中最优利润值为8-17简单起见只考虑0到100000之间的整数价格。
#include cstdioint data [100005];int main () {int result 0;int n 0;while (scanf (%d, data [n]) ! EOF) n;for (int i 0; i n; i) {for (int j i 1; j n; j) {int val data [j] - data [i];if (result val) result val;}}return 0;
}
题目2、爱吃鬼
小艺酱每天都在吃和睡中浑浑噩噩地度过。可是肚子是有空间上限v的。小艺酱有n包零食每包零食占据肚子空间a [i]并会给小艺酱一个甜蜜值 b [i]。小艺酱想知道自己在肚子空间上限允许范围内最大能获得的甜蜜值是多少?
#include cstdioint a [1005];
int b [1005];
int dp [1005];int main () {int v, n;scanf (%d %d, v, n);for (int i 0; i n; i) scanf (%d %d, a [i], b [i]);for (int i 0; i n; i) {for (int j a [i]; j v; j) {dp [j] max (dp [j], dp [j - a [i]] b [i]);}}printf (%d, dp [v]);return 0;
}
题目3、开学趣闻之美食诱惑
小艺酱又开学了可是在上学的路上总会又各种意想不到的美食诱惑让小艺酱迟到。假设小艺酱家到学校是一个n*n的矩阵。每个格子包含一个诱惑值p诱惑着小艺让她迟到。小艺位于矩阵的左上角学校在矩阵的右下角。小艺想知道自己到达学校所要经历的最小诱惑值是多少
int main () {int n;scanf (%d, n);int data [n][n];for (int i 0; i n; i) {for (int j 0; j n; j) {scanf (%d, data [i][j]);}}int dp [n][n];dp [0][0] data [0][0];for (int i 1; i n; i) dp [0][i] dp [0][i - 1] data [0][i];for (int i 1; i n; i) dp [i][0] dp [i - 1][0] data [i][0];for (int i 1; i n; i) {for (int j 1; j n; j) {dp [i][j] min (dp [i - 1][j], dp [i][j - 1]) data [i][j];}}return 0;
}
刚开始角色位于(0, 0)位置且必定吃到左上角起始位置处的诱惑值。
接下来角色可以向右或者向下走先分别计算出来仅向右走和仅向下走能吃到的诱惑值。
边界计算完成之后就可以进入地图内部进行计算了。例如从(0,0)走到(1,1)有两种方法先向右后向下和先向下后向右这时就可以利用之前算好的边界条件的值了。假设先向右后向下那么先从(0,0)走到(0,1)再从(0,1)走到(1,1)。这个过程中从(0,0)走到(0,1)已经计算过了直接用计算好的结果加上(1,1)处的诱惑值即可。这也就是动态规划算法的核心思想了将计算过的数据存起来后面的计算可以用上前面计算出来的结果减少重复计算的时间提升效率。
动态规划算法从小规模问题扩展到大规模的问题每一步存储的都是当前规模下的最优解。全部计算完成之后输出右下角那个格子上的诱惑值即可这就是从左上角到右下角的最小诱惑值。
有小伙伴私信问博主为什么不能向左或者向上走这个其实是题目描述的问题了这道题的原型是机器人寻路问题这是学动态规划时的一道标准例题在网上通过教程自学动态规划的小伙伴可能多少会对这道题有点印象。
机器人路径问题https://blog.csdn.net/weixin_45975835/article/details/117331825
可以参考一下这位博主写得文章。
题目4、小艺照镜子
已知字符串str。输出字符串str中最长回文串的长度。
int match (std::string str) {int result 1;for (int i 0; i str.length (); i) {for (int j 0; j 2; j) {int left i - j;int right i 1;while (left -1 right str.length () str [left] str [right]) {left--;right;}int len right - left - 1;if (result len) result len;}}return result;
}
直接从左向右查找回文串时间复杂度为O(N^3)会超时。
使用中心扩展法从每个位置向两边查找不是回文串就停下这样可以将复杂度优化到O(N^2度。
查找时回文串分为奇回文串aba和偶回文串abba这里需要分别计算两种情况下的回文串长度。如果当前位置无法向左向右扩展成回文串那么它的长度是1这个字符本身构成一个回文串例如 a 自身可以构成一个长度为 1 的回文串。
