C++ 打家劫舍变种

前言：没做过打家劫舍的先把NC230032做了再来做此题

看示例3，a=[1,1,2,2,2,2,2,3,3],如果我们选了一个等于2的数字，那么所有1和3都会被删除，所以选了一个2以后，所有2都要选

将ak删除后相邻的元素也删除，联想到不能选相邻的，即打家劫舍

把a转换成值域数组b，b[i]表示a中等于i的元素之和，示例三中有0个0，2个1，5个2，2个3，那么b=[0,2*1,5*2,2*3];

然后套用打家劫舍的代码即可

定义dp[i]为a数组最大数字为i可获得的最大分数 选当前分数dp[i]=dp[i-2]+b[i],不选dp[i]=dp[i-1] 取最大值

实现时为了防止越界可以将dp数组预留两个0，转移方程:dp[i+2]=max(dp[i]+b[i],dp[i-1])

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
int b[100100],dp[100100];
signed main() {
  int n,mx=0;
  cin>>n;
  for(int i=0;i<n;i++){
    int x;
    cin>>x;
    b[x]+=x;//需要一个序列
	mx=max(mx,x);//最大分数下标 比如示例3就是3
  }
  for(int i=0;i<=mx;i++){
  dp[i+2]=max(dp[i+1],dp[i]+b[i]);
  }
  cout<<dp[mx+2];
}