题解 | #删除相邻数字的最大分数#

解题思路：

• 做之前处理下数据，数据的大小是1E4，开一个数组建立一个桶v，对于输入的每一个数据，以数据值做下标，对应的桶数值++即可，再讲输入的数丢入一个set中，习惯操作vector，又将数丢到了v2中，操作的时候只要在这个set中的每一个数依次向后动态规划即可。
• 从左往右考虑，在i行进的过程中，如果i=0则$dp[0]=v2[0]\ast v[v2[0]]dp[0]\; =\; v2[0]*v[v2[0]]$接下来只要分析$v2[i]-v2[i-1]==1?v2[i]-v2[i-1]\; ==\; 1?$，如果相等则有$dp[i]=max(dp[i-1],i==1?v2[i]\ast v[v2[i]]:v2[i]\ast v[v2[i]]+dp[i-2])dp[i]\; =\; max(dp[i-1],\; i==1?v2[i]*v[v2[i]]:v2[i]*v[v2[i]]\; +\; dp[i-2])$,即当两个值之差是1的时候，要么取前值，要么取后值。如果不满足条件则有：$dp[i]=dp[i-1]+v2[i]\ast v[v2[i]]dp[i]\; =\; dp[i-1]\; +\; v2[i]*v[v2[i]]$，即直接把当前值以及它的个数提取出来就好了。

#include<bits/stdc++.h>
using namespace std;
int v[10009];
long long solve(vector<int> &v2, int i, vector<long long> &dp){//递归
    if(dp[i] != 0) return dp[i];
    if(i == 0) dp[i] = v2[i] * v[v2[i]];
    else {
        if(v2[i] - v2[i-1] == 1) dp[i] = max(solve(v2,i-1, dp), i==1?v2[i]*v[v2[i]]:v2[i]*v[v2[i]]+solve(v2,i-2,dp));
        else dp[i] = solve(v2,i-1,dp)+v2[i]*v[v2[i]];
    }
    return dp[i];
}
long long solve2(vector<int> &v2, vector<long long> &dp){//递推
    dp[0] = v2[0]*v[v2[0]];
    for(int i = 1; i < v2.size();++i){
      //如果前后两值之差为一，那只能选其一。
        if(v2[i] - v2[i-1] == 1) dp[i] = max(dp[i-1], i==1?v2[i]*v[v2[i]]:v2[i]*v[v2[i]] + dp[i-2]);
        else dp[i] = dp[i-1] + v2[i]*v[v2[i]];
    }
    return dp[v2.size()-1];
}
int main(){
    int n;
    cin>>n;
    set<int> st;
    for(int i = 0; i < n; ++i){
        int tmp;
        cin>>tmp;
        v[tmp]++;
        st.insert(tmp);
    }
    vector<int> v2;
    for(auto i:st){
        v2.push_back(i);
    }
    vector<long long > dp(v2.size());
    long long ans ;
    // ans = solve(v2, v2.size()-1, dp);
    ans = solve2(v2, dp);
    cout<<ans<<endl;
    return 0;
}