【算法手记12】DP25 删除相邻数字的最大分数

2025/4/18 3:33:10 来源：https://blog.csdn.net/weixin_72357342/article/details/147076495 浏览: 次关键词：【算法手记12】DP25 删除相邻数字的最大分数

🦄个人主页:修修修也

🎏所属专栏:刷题

⚙️操作环境:牛客网

目录

一.DP25 删除相邻数字的最大分数

题目详情:

题目思路:

解题代码:

结语

一.DP25 删除相邻数字的最大分数

牛客网题目链接(点击即可跳转):DP25 删除相邻数字的最大分数

题目详情:

本题详情如下图:

题目思路:

本题解题思路如下:

        这道题首先我们要处理一下原数据,因为原数组并不方便我们操作相邻的两个数,所以我们创建一个哈希表来统计一下所有数它出现的次数以及它本身相乘的"权值".

        然后还是利用动态规划解题,本题特殊的点在于需要填两个动态规划dp表,一个是选i位置数的dp表f[i], 一个是选i位置数的dp表g[i]. 这两个dp表的递推方程分别如下:

f[i] = hash[i] + g[i-1]    (表示选i位置的价值 = i位置本身权重+不选i-1位置的数的最大利益)
g[i] = max(g[i-1], f[i-1]) (不选i位置时价值 = 选i-1位置和不选i-1位置里大的那个)

解题代码:

本题解题代码如下

#include <iostream>
using namespace std;int main() 
{int n;cin>>n;int hash[10001]={0};for(int i=0;i<n;i++){int tmp;cin>>tmp;hash[tmp]+=tmp;}long long f[10001]={0};long long g[10001]={0};for(int i=1;i<10001;i++){f[i]=hash[i]+g[i-1];g[i]=max(g[i-1],f[i-1]);}cout<<max(f[10000],g[10000]);
}