題意：給你n個(gè)數(shù)字ai（1<=ai<=10^5）吨拍，如果你選擇x則x-1與x+1不能選，計(jì)算你能獲得的最大值（數(shù)字可重復(fù)）
題解：因?yàn)閍i的范圍很小网杆，直接將ai作為數(shù)組索引羹饰，用狀態(tài)轉(zhuǎn)移方程從前往后遞推出dp[maxx]的值 即dp[i] = max(dp[i-2]+cnt[i]*i , dp[i-1]); 別忘了初始化dp[0] = 0; dp[1] = cnt[1];
WA了兩次，第一次沒(méi)有用long long碳却，第二次只對(duì)dp數(shù)組用了long long但中間過(guò)程沒(méi)有強(qiáng)制轉(zhuǎn)換導(dǎo)致溢出队秩；
代碼:
#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;
}
