竞赛总览

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

竞赛题解

题目1、鬼画符门之宗门大比

给定整数序列A，求在整数序列A中连续权值最大的子序列的权值。

经典的子序列问题，和第二十一期考过的连续子数组的最大和一题解法相似。

维护一个临时变量，用于求和。

利用贪心的思想，当临时变量非负时，当前累加和等于临时变量加上当前项。否则，抛弃前面的累加和（因为它是负的，只会越加越小），直接使用当前项，作为新的序列累加和起点。

每次更新完累加和时，判断它是否超过了历史极值，如果达到条件则更新历史极值。

当循环扫描完所有输入数据时，即可得到最大累加和。

题目2、K皇把妹

存在n个节点，目标节点在m。每个节点有自己的权值a。在权值k内（含权值k）选择一个权值非0节点且与目标节点距离最近，节点i与节点j的距离为abs(i-j)。

for (int i = 1; i <= n; i++) scanf ("%d", &data [i]);
for (int i = 1; i <= n; i++) {if (data [i] == 0) continue;if (data [i] <= k) result = min (result, abs (m - i));
}

和上一题的代码框架基本一致，只是求累加和改为了求当前项到目标节点的距离。

另外，按照题目要求，权值必须非0且不超过k才能作为可选项来考虑，所以如果是零就直接跳过这一项即可。

题目3、影分身

已知字符串str包含字符’x’,’y’。如果相邻的两个字符不同，消除两个字符。优先从左边进行消除。

这道题可以直接模拟，但是更好的方法是统计x和y的个数。

由于题目规定只要相邻的两个字符不同就可以消除，因此，无论x和y如何摆放，总会有一对相邻的x和y出现在某个位置，并被消除。如此往复，较少的那种字符一定会被清除，剩下较多的字符。

题目4、开心的金明

金明今天很开心，家里购置的新房就要领钥匙了。新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1-5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。请你帮助金明设计一个满足要求的购物单。

背包问题，题目中有一句话非常关键：每件物品的价格与重要度的乘积的总和最大。

使用动态规划算法，将每件物品分别往背包里塞。从空背包开始更新状态（容量为N），动态地更新每种容量下的背包最大价值即可。