dp 俩种状态。dp[i][0] 表示不取，dp[i][1]表示取
如果i取 那么dp[i][1] = dp[i - 1][0] + s[i]
如果i 不取 dp[i][0] = Max(dp[i -1][0],dp[i - 1][1]
注意数据范围。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef __int64 ll;
int const MAXN = 100010;
ll dp[MAXN][2],s[MAXN];
inline ll Max(ll a,ll b){
return a>b?a:b;
}
int main(){
int n;
scanf("%d",&n);
memset(s,0,sizeof(s));
for(int i = 1;i <= n;i++){
int x;
scanf("%d",&x);
s[x] += x;
}
memset(dp,0,sizeof(dp));
for(int i = 1;i <= 100001;i++){
dp[i][0] = Max(dp[i - 1][1],dp[i - 1][0]);
dp[i][1] = dp[i - 1][0] + s[i];
}
printf("%I64d\n",dp[100001][0]);
return 0;
}