Boredom（简单dp）

Description

Alex doesn't like boredom. That's why whenever he gets bored, he comes up with games. One long winter evening he came up with a game and decided to play it.

Given a sequence a consisting of n integers. The player can make several steps. In a single step he can choose an element of the sequence (let's denote it ak) and delete it, at that all elements equal to ak + 1 and ak - 1 also must be deleted from the sequence. That step brings ak points to the player.

Alex is a perfectionist, so he decided to get as many points as possible. Help him.

Input

The first line contains integer n (1 ≤ n ≤ 10^5) that shows how many numbers are in Alex's sequence.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 10^5)

Output

Print a single integer — the maximum number of points that Alex can earn.

Sample Input

9
1 2 1 3 2 2 2 2 3

Sample Output10


分析：很容易观察到数据的先后是不影响值的大小的，所以我们不妨先用一个桶排序。
接下来再看这个问题：对于每个数字我们有两种选择：选还是不选，而且前面数字的选对后面（差大于1）的数字是没有影响的，即无后效性，考虑dp。
假如我们用数组dp[i]保存数据i的状态，考虑从左往右进行分析（类似背包问题，每个物品选还是不选）
对第i个物品，假如我们选这个物品，那么dp[i]=dp[i-2]+a[i]*i(之前的分数加上这次的分数)
如果我们不选这个物品，那么dp[i]=dp[i-1]（因为没有选择所以分数不变）
那么状态转移方程就是dp[i]=max(dp[i-1],dp[i-2]+a[i]*i)

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 typedef long long ll;
 7 const int MAXN=1e5+5;
 8 ll a[MAXN];
 9 ll dp[MAXN];
10 ll n,x,maxn;
11 ll ans;
12 
13 int main()
14 {
15     while(scanf("%lld",&n)!=EOF)
16     {
17         maxn=0; ans=0;
18         memset(a,0,sizeof(a));
19         for(int i=0;i<n;i++)
20         {
21             scanf("%lld",&x);
22             if(maxn<x) maxn=x;
23             a[x]++;
24         }
25         memset(dp,0,sizeof(dp));
26         dp[1]=a[1];
27         for(ll i=2;i<=maxn;i++)
28         {
29             dp[i]=max(dp[i-1],dp[i-2]+a[i]*i);
30             //ans=max(ans,dp[i]);
31         }
32         printf("%lld
",dp[maxn]);
33     }
34     return 0;
35 }

AC Code

前面wa了好多次，记录一下错因：

　1.忘记开long long (有可能10^5*10^5)

　2.用ans保存结果忘记分析循环无法执行的情况（自闭）

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 typedef long long ll;
 7 const int MAXN=1e5+5;
 8 ll a[MAXN];
 9 ll dp[MAXN];
10 ll n,x,maxn;
11 ll ans;
12 
13 int main()
14 {
15     while(scanf("%lld",&n)!=EOF)
16     {
17         maxn=0; ans=0;
18         memset(a,0,sizeof(a));
19         for(int i=0;i<n;i++)
20         {
21             scanf("%lld",&x);
22             if(maxn<x) maxn=x;
23             a[x]++;
24         }
25         memset(dp,0,sizeof(dp));
26         dp[1]=a[1];
27         for(ll i=2;i<=maxn;i++)
28         {
29             dp[i]=max(dp[i-1],dp[i-2]+a[i]*i);
30             ans=max(ans,dp[i]);
31         }
32         printf("%lld
",ans);
33     }
34     return 0;
35 }

Wa Code