DP Codeforces Round #260 (Div. 1) A. Boredom

时间：2024-01-17 15:26:26

题目传送门

 /*

     题意：选择a[k]然后a[k]-1和a[k]+1的全部删除，得到点数a[k]，问最大点数

     DP：状态转移方程：dp[i] = max (dp[i-1], dp[i-2] + (ll) i * cnt[i]);

         只和x-1，x-2有关，和顺序无关，x-1不取，x-2取那么累加相同的值，ans = dp[mx]

 */

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <iostream>

 #include <cmath>

 using namespace std;

 typedef long long ll;

 const int MAXN = 1e5 + ;

 const int INF = 0x3f3f3f3f;

 ll dp[MAXN];

 int cnt[MAXN];

 int main(void)        //Codeforces Round #260 (Div. 1) A. Boredom

 {

     int n;

     while (scanf ("%d", &n) == )

     {

         memset (dp, , sizeof (dp));

         memset (cnt, , sizeof (cnt));

         int x, mx = ;

         for (int i=; i<=n; ++i)    {scanf ("%d", &x);    cnt[x]++;    if (mx < x) mx = x;}

         dp[] = cnt[];

         for (int i=; i<=mx; ++i)

         {

             dp[i] = max (dp[i-], dp[i-] + (ll) i * cnt[i]);

         }

         printf ("%I64d\n", dp[mx]);

     }

     return ;

 }

 /*

 2

 1 2

 3

 1 2 3

 9

 1 2 1 3 2 2 2 2 3

 */

相关文章