题目链接

https://ac.nowcoder.com/acm/contest/9667/J

解题思路

一开始还以为选奇数或偶数权值最大的就行嘞，结果发现是错的，比如1，4，可以两个都选，并不是只能选奇数或者偶数。
简单dp；
dp[i][1/0]表示第i个数选还是不选；但是这里的第i个数并不是a数组的下标i。
首先，输入的时候统计每个数的个数；
我们再对整个数组从小到大排序，进行类离散化处理，比如8，1，1，6，7，6，1，8，处理之后为1，6，7，8，dp的下标i=1对应的1，i=2对应6……；
转移方程：
若第i个比第i-1个大1，此时i和i-1只能选一个，所以转移方程为dp[i][0]=max(dp[i-1][0],dp[i-1][1]),dp[i][1]=dp[i-1][0]+(ll)a[i]*cnt[a[i]]
否则，dp[i][0]=max(dp[i-1][0],dp[i-1][1]),dp[i][1]=dp[i][0]+(ll)a[i]*cnt[a[i]];

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10;

ll ans,dp[N][2];
int n,a[N],cnt[N];

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],cnt[a[i]]++;
    sort(a+1,a+n+1);
    n=unique(a+1,a+n+1)-a-1;//类离散化
    for(int i=1;i<=n;i++)
    {
        if(a[i]==a[i-1]+1)
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]),
        dp[i][1]=dp[i-1][0]+(ll)a[i]*cnt[a[i]];//勿忘乘个数
        else 
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]),
        dp[i][1]=dp[i][0]+(ll)a[i]*cnt[a[i]];//勿忘乘个数
        ans=max(ans,max(dp[i][0],dp[i][1]));
    }
    cout<<ans<<endl;
}