(dp)Boredom CodeForces - 455A

题意：给你n个数字ai（1<=ai<=10^5），如果你选择x则x-1与x+1不能选，计算你能获得的最大值（数字可重复）
题解：因为ai的范围很小，直接将ai作为数组索引，用状态转移方程从前往后递推出dp[maxx]的值 即dp[i] = max(dp[i-2]+cnt[i]*i , dp[i-1]); 别忘了初始化dp[0] = 0; dp[1] = cnt[1];
WA了两次，第一次没有用long long，第二次只对dp数组用了long long但中间过程没有强制转换导致溢出；
代码:

#include<algorithm>
#include <iostream>
#include  <cstdlib>
#include  <cstring>
#include  <cassert>
#include   <cstdio>
#include   <vector>
#include   <string>
#include    <cmath>
#include    <queue>
#include    <stack>
#include      <set>
#include      <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
//#define INF 0x3f3f3f3f
typedef pair<int,pair<int,int> >pii;//注意空格呦！ 
typedef long long ll;
const ll mod = 1000000007;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
const int INF=0x7f7f7f7f;
const int maxn = 1e5+5;

int cnt[maxn];
long long dp[maxn];
int n,a,sum = 0,maxx = 0;


int main(){
    memset(cnt,0,sizeof(cnt));
    scanf("%d", &n);
    rep(i,1,n){
        scanf("%d", &a);
        cnt[a]++;
        maxx = max(maxx,a);
    }
    dp[0] = 0,dp[1] = cnt[1];
    rep(i,2,maxx)
        dp[i] = max(dp[i-2] + (long long)cnt[i]*i, dp[i-1]);
    printf("%I64d", dp[maxx]);
    return 0;
}