CSDN 编程竞赛三十一期题解

竞赛总览

CSDN 编程竞赛三十一期：比赛详情 (csdn.net)

本次竞赛的最后一道题的描述部分有些问题（题目描述与样例不符），另外，测试数据似乎也有点问题，试了多种方式，但最多只能通过10%的测试点。竞赛体验较差，希望之后的竞赛开始前能够对测试数据进行验证，不要再发生这种情况了。

竞赛题解

题目1、最优利润值

你在读的经营课程上，老师布置了一道作业。在一家公司的日常运营中，会对一些商品的价格走势根据一些经验和数据进行预估，并据此进行决策。例如，假设某商品每天的价格都有可能变动，我们要做的就是低买高卖获得最高利润。比如，假设我们预估该商品接下来七天内的价格走势如下：4 1 2 3 6 4 8，那我们采取的最佳策略是在价格1块钱的时候买入，在价格8块钱的时候卖出。为了简化整个过程，我们限定在此周期内只能有一次买入、一次卖出，且商品在没有购入前是无法卖出的，即该商品不是期货而是现货。现要求你用程序来实现自动决策。输入一定天数的商品预估价格，自动计算出最优利润值。例如，上面的例子中，最优利润值为8-1=7。为了简单起见，只考虑0-100000之间的整数价格。

#include <cstdio>int 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;}}printf ("%d", result);return 0;
}

题目2、开学趣闻之美食诱惑

小艺酱又开学了，可是在上学的路上总会又各种意想不到的美食诱惑让小艺酱迟到。假设小艺酱家到学校是一个n*n的矩阵。每个格子包含一个诱惑值p，诱惑着小艺，让她迟到。小艺位于矩阵的左上角，学校在矩阵的右下角。小艺想知道自己到达学校所要经历的最小诱惑值是多少。

#include <cstdio>int min (int a, int b) {if (a < b) return a;return b;
}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];}}printf ("%d", dp [n - 1][n - 1]);return 0;
}

这个题型和动态规划初学者的例题一样，非常经典（不亚于打家劫舍系列），学过动态规划的小伙伴应该都知道它的解法。

使用一个数组维护从原点到每个格子上的诱惑值，第i行、第j列的那个格子，可以从它的上面或者左面坐过来，因此它的诱惑值为它上面和左面格子诱惑值的最小值，加上它自己本身的诱惑值。

从原点开始，不断扩大计算范围，并将计算结果存储到数组中，最后走到终点时即可得到答案。

题目3、小艺照镜子

回文串是一个正读和反读都一样的字符串。已知字符串str，输出字符串str中最长回文串的长度。

#include <cstdio>
#include <iostream>
#include <string>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, 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;
}int main () {std::string str;std::cin >> str;printf ("%d", match (str));
}

这道题之前也考过，测试数据比较友好，不需要使用马拉车算法。但也不能直接暴力，否则复杂度为O(N^3)，之前已经试过了，会超时。可以使用中心扩展法完成此题。

题目4、爱吃鬼

小艺酱每天都在吃和睡中浑浑噩噩的度过。可是小艺酱的肚子是有空间上限v的。小艺酱有n种零食，每包零食占据小艺酱肚子空间a [i]，并会给小艺酱一个甜蜜值b [i]。小艺酱想知道在自己的肚子空间上限允许范围内，最大能获得的甜蜜值是多少。

背包问题。测试数据有问题，无法通过此题，代码就不放了。