撰写题意：给你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但中间过程没有强制转换导致溢出； 代码: [cpp] #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; } [/cpp]
