题解：2018级算法第二次上机 Zexal的竞赛

题目描述：

样例：

实现解释：

一道需要一点思考的动态规划题目

知识点：动态规划，数据记录

首先将题目描述调整：分别输入不同分数的题目总分（便于后续计算），当获得了i分数的总分后无法获得i-1和i+1的总分。

于是便可先利用score[i]储存i分数的总分数，用dp[i]储存以前i个分数为范围进行题目选择时的最大可获得分数。dp便是动态规划所用的数组。

于是可得状态转移方程如下：

dp[0] = score[0]; dp[1] = score[1];

dp[i] = max(dp[i-2]+score[i],dp[i-1]);

0和1分直接初始化，而选择前i个分数时的最大分数有两种选择：1.选择前i-1个分数时的最大分数，2.选择前i-2个分数时的最大分数加上当前分数的总分。选择最大的作为i时的最大值即可实现最大值的循环获取。

最后将其完善为完整的代码即可。

坑点：

多组输入时需要重置score数组为0

考虑到dp是从前向后进行，因此注意要重置dp数组的0和1处的值

完整代码：

//动态规划 zexal的竞赛

#include <iostream>

#include <algorithm>//引用max函数

using namespace std;

long long dp[100010];

long long score[100010];

//注意如果多次输入需要对score进行清空处理

int main()

{

	ios::sync_with_stdio(false);

	int n,s;

	cin >> n;//题目个数

	int top = 0;//最大的题目分数，防止无用的遍历

	for (int i = 0;i<n;i++)

	{

		cin >> s;

		score[s]+=s;//出现x次，则做完为x*s分

		if(s>top) top = s;

	}

	dp[0] = score[0];

	dp[1] = max(score[0],score[1]);

	for(int i = 2;i<=top;i++)

	{

		//具体状态转换方程见实现解释

		dp[i] = max(dp[i-2]+score[i],dp[i-1]);

	}

	//以所有分数题目为范围的最大分数

	cout << dp[top] << '\n';

}

巴特西

题解：2018级算法第二次上机 Zexal的竞赛

题目描述：

样例：

实现解释：

完整代码：

最新文章

热门文章