1 /* 2     题意：选择a[k]然后a[k]-1和a[k]+1的全部删除，得到点数a[k]，问最大点数 3     DP：状态转移方程：dp[i] = max (dp[i-1], dp[i-2] + (ll) i * cnt[i]); 4         只和x-1，x-2有关，和顺序无关，x-1不取，x-2取那么累加相同的值，ans = dp[mx] 5 */ 6 #include 
     
       7 #include 
      
        8 #include 
       
         9 #include 
        
         10 #include 
         
          11 using namespace std;12 13 typedef long long ll;14 const int MAXN = 1e5 + 10;15 const int INF = 0x3f3f3f3f;16 ll dp[MAXN];17 int cnt[MAXN];18 19 int main(void)        //Codeforces Round #260 (Div. 1) A. Boredom20 {21     int n;22     while (scanf ("%d", &n) == 1)23     {24         memset (dp, 0, sizeof (dp));25         memset (cnt, 0, sizeof (cnt));26 27         int x, mx = 0;28         for (int i=1; i<=n; ++i)    {scanf ("%d", &x);    cnt[x]++;    if (mx < x) mx = x;}29 30         dp[1] = cnt[1];31         for (int i=2; i<=mx; ++i)32         {33             dp[i] = max (dp[i-1], dp[i-2] + (ll) i * cnt[i]);34         }35 36         printf ("%I64d\n", dp[mx]);37     }38 39     return 0;40 }41 42 43 44 /*45 246 1 247 348 1 2 349 950 1 2 1 3 2 2 2 2 351 */