C2-Zexal的竞赛

题目描述

在一场竞赛中有n">n道题目，每道题都会对应一个分值，你可以选择任意一道题作答，比如你选择了x">x分的题目，那么在作答完毕（假设一定可以得分）后，你将获得x分，但是这场比赛中分值等于x−1">x?1和x+1">x+1的其他题目就会消失，那么这场比赛中你最多可以得到多少分？

输入

第一个数为题目总数n（0<n<1e5)">n（0<n<1e5)

接下来为n个">n个整数a1，a2，a3.....(0<ai<1e5)">a1，a2，a3.....(0<ai<1e5)

输出

输出你可以得到的最高分

输入样例

9
1 2 1 3 2 2 2 2 3

输出样例

10

样例解释

每次都选择2 选择5次即可得到10分 1和3根据题目要求会消失

代码

#include 
#include 
#include <string.h>
using namespace std;
int n,dp[100005][2],a[100005],mod = 1000000007;
int main()
{
    while(~scanf("%d",&n))
    {
        memset(a, 0, sizeof(a));
        memset(dp, 0, sizeof(dp));
        int maximum = 0, ans = 0;
        for(int i = 0; i < n; i++)
        {
            int t;
            scanf("%d",&t);
            a[t]++;
            maximum = max(t,maximum);
        }
        for(int i = 1; i <= maximum; i++)
        {
            dp[i][1] = dp[i-1][0] + i*a[i];　　　　　　//选这道题，获得这道题的分值和不选上一道题的分值
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]);　　// 不选这道题，获得上一道题的分值
            ans = max(max(dp[i][1], dp[i][0]), ans);
        }
        printf("%d\n",ans);
    }
    return 0;
}