Codeforces Round #260 (Div. 1) Problem: 455A - Boredom

はじめに

codeforcesの問題に取り組んでいます。
この問題は正解者が３万人近くいるのに1500点問題なのでトライしてみました。
2014年のコンテストの問題です。

問題

Problem - 455A - Codeforces

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 ≤ 105) that shows how many numbers are in Alex's sequence.

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

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

数列Aの中からAKを選択すると得点AKが得られますが数列中のAK+１とAK-1を全部削除しなければなりません。得点が最大になるようにしたときの得点の最大値を求めます。

考察

最初は大きい方から貪欲にとっていけばいいのではないかと考えましたがサンプル３で間違いに気づきました。選択した数字の前後は使えませんが，選択した数字自体はすべて得点できます。

そうすると（２個小さいところまでの得点の最大値に現在注目している数字にその個数を掛けたもの）と（１個小さいところまでの得点の最大値）のmaxをとるdpを組めばよいことがわかります。
数字の制約は10^5なので計算量も大丈夫です。

最初に各数字の出てくる数をc[x]という配列にした上で次の漸化式でdpします。

dp[x]=max(dp[x-1],dp[x-2]+c[x]*x)

dp[0]は0，dp[1]はc[1]*1=c[1]です。

結果は最大10^10程度になるためlong longを使います。

提出コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
ll dp[100010];
ll c[100010];

int main(){
  int n;
  cin>>n;
  map<int,int>mp;
  int a[n];
  rep(i,n){
    cin>>a[i];
    mp[a[i]]++;
  }
  for(int i=0;i<100010;i++){
    c[i]=mp[i];
  }
  dp[0]=0;
  dp[1]=mp[1];
  for(int i=2;i<100010;i++){
    dp[i]=max(dp[i-1],dp[i-2]+c[i]*i);
  }
  cout<<dp[100001]<<endl;
  return 0;
}