CFR 260 1A. Boredom ( DP )

Problem - 455A - Codeforces
First sort and compress the items. Now we will find that if a number x is to be taken, it will only affect that it might be illegal to take x - 1 or x + 1. So it is only possible to transfer to the next state that is larger than x + 1, which will also cover the problem of x - 1.
開始寫這些題目是因為大神的PPT
演算法／陳伯恩

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXA = 1e5 + 5;
typedef pair< int, int > pii;
typedef long long ll;

int n;
int a[ MAXN ];

ll dp[ MAXN ];

void solve(){
    sort( a, a + n );
    vector< pii > item;
    for( int i = 0; i < n; ){
        int j = i; while( j + 1 < n && a[ j + 1 ] == a[ j ] ) ++j;
        item.push_back( pii( a[ j ], j - i + 1 ) );
        i = j + 1;
    }
    for( int i = 0; i < item.size(); ++i ){
        if( item[ i ].first + 1 == item[ i + 1 ].first ){
            if( i + 1 == n ) dp[ n ] = max( dp[ n ], (ll)item[ i ].first * item[ i ].second + dp[ i ] );
            else dp[ i + 2 ] = max( dp[ i + 2 ], (ll)item[ i ].first * item[ i ].second + dp[ i ] );
        } else
            dp[ i + 1 ] = max( dp[ i + 1 ], (ll)item[ i ].first * item[ i ].second + dp[ i ] );
        dp[ i + 1 ] = max( dp[ i + 1 ], dp[ i ] );
    }
    cout << dp[ (int)item.size() ] << "\n";
}

int main(){
    scanf("%d", &n);
    for( int i = 0; i < n; ++i )
        scanf("%d", a + i);
    solve();
    return 0;
}