本文共 1167 字，大约阅读时间需要 3 分钟。

题目大意：

       给定一个含有n个整数的数组，你可以进行多次操作，每次操作从数组选一个数a[k]，然后将其删除，然后删除与a[k]-1和a[k]+1相等的数，然后可以得到a[k]分，求进行多次操作后得到的最多的分。

题解：

      设dp[i]表示当前删除的最大数字为i时得到的最大得分

       dp[i]=max(dp[i-1],dp[i-2]+i*num[i]);   num[i]是数字i出现的次数

对于当前值为i的数，只有选和不选两种情况

        dp[i-1]是不选第i个

        dp[i-2]+cnt[i]*i 选第i个

        这里大家可能会有疑问，题中说删了ak的话，ak-1和ak+1也都会被删掉，但是这个状态转移方程却只考虑了ak-1，那么ak+1呢？也就是说当前的选择会对后来造成影响。

        如果选了第i个数，那么其实就默认，第i+1个数不能选了；

        而取第i+1个数，也是在默认第i个数没有选。   

        这就代表了2种可能的情况，选第i+1个和不选第i个(也就是转移方程中的dp[i-1]相对应)，就像我们选第i个的时候和dp[i-2]相对应，我们选第i+1个的时候是和dp[i-1]对应的。

       既然相对应包含在了转移方程里，那么我们就不同再多余考虑了。

       dp只是一种优雅的暴力枚举方式，在计算的时候取最大值，如果取第i个数是能到最大值的方法的话，取第i+1个数得到的值一定比取第i个数小。

    至于到底选哪种，让ans=max(ans,dp[i]);这句话来选择吧

#include
   
    #include
    
     using namespace std;#define ll long longll a[100010];ll num[100010];ll dp[100010];int main(){    int n;    scanf("%d",&n);    ll maxx=0;    for(int i=1;i<=n;++i)    {        scanf("%I64d",&a[i]);        ++num[a[i]];        maxx=max(maxx,a[i]);    }    ll ans=0;    //dp[i]表示当前删除的最大数字为i时得到的最大得分    dp[0]=0;dp[1]=num[1];    for(int i=2;i<=maxx;++i)    {        dp[i]=max(dp[i-1],dp[i-2]+i*num[i]);        //dp[i-1]是不选第i个        //dp[i-2]+cnt[i]*i 选第i个        ans=max(ans,dp[i]);    }    printf("%I64d\n",ans);    return 0;}
    
   

转载地址：http://ikfgf.baihongyu.com/