[算法题]删除相邻数字的最大分数

题目链接: 删除相邻数字的最大分数

用动态规划求解, 根据题意选择 a, 那么 a-1 和 a+1 的值都不能选, 那首先通过一个哈希表来存储数据中每个值出现的总和, 接着定义状态表示:

通过哈希表的映射关系, 可以快速知道某一个值出现的总和, 可以定义两个状态表示:

select[i]: 表示遍历到 i 位置, 该位置的值必选, 其最大值是多少.

unselect[i]: 表示遍历到 i 位置, 该位置的值不选, 其最大值是多少.

那么状态转移方程为:

在哈希表中, key 为下标, 下标代表的就是数据中的某个值, val 为 hash[i], 也就是该值出现的总和, 比如下标为 2, hash[2] = 10, 就表示数据中存在 5 个 2, 那么 5 个 2 的总和就是 10, 而状态转移方程遍历的就是 hash 表, 则为:

select[i] = unselect[i - 1] + hash[i] (i 位置的值必选, 那么根据题意 i - 1 的值是不能选的)

unselect[i] = max(select[i - 1], unselect[i - 1]) (i 位置的值不选, 那么根据题意 i - 1 的值可以选, 也可以不选, 所以要取选或者不选的较大值)

不用特殊处理初始化, 都是 0 即可, 也不一定要使用 map/unordered_map 等容器, 因为题中元素大小不大, 可以利用数组模拟哈希表, 也不一定要创建两个数组进行状态递推, 可以通过 4 个变量分别记录选与不选的前一个值和选与不选的当前值即可, 题解代码如下:

#include <iostream>
using namespace std;

int main() 
{
    int n;
    cin >> n;
    int hash[10001] = {0};
    int num = 0;
    for(int i = 0; i < n; ++i)
    {
        cin >> num;
        hash[num] += num;
    }

    int select = 0;
    int unselect = 0;
    int select_before = select;
    int unselect_before = unselect;
    for(int i = 1; i <= 10000; ++i)
    {
        select_before = select;
        select = unselect + hash[i];
        unselect = max(select_before, unselect_before);
        unselect_before = unselect;
    }
    cout << max(select, unselect) << endl;
    return 0;
}