Algoogle

Algorithm for Programming Contest

Codeforces 455A Boredom

Category: Codeforces Tag: dp

Boredom

問題概要

長さnの数列aがある.
aのあるk番目を取り除くとき, a[k]-1, a[k]+1の値を取る場所も全て取り除く.
このとき得点a[k]を得る.
これを繰り返すとき, 得られる得点の総和の最大はいくらになるか.

解法

まず各値は数列中に何個含まれるかしらべる.
そうするとある値a[k]を取ったとき, a[k]-1とa[k]+1が消えることから他のa[k]は全て取れる.
また前を決めれば後ろも決められるのは明らかなので, 小さい数から順に見ていき
dp[k+1][0] := k番目を取らないときの最大
dp[k+1][1] := k番目を取るときの最大
とDPすればよい.

コード

(455A.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i,a) repi(i,0,a)
const double eps = 1e-9;
const int inf = 1e9;
typedef long long ll;
typedef pair<int,int> pii;

int n, a[100010], l, r;
ll scr[100010], dp[100010][2];

ll solve(){
    l = a[0]; r = a[0];
    rep(i,n){
        scr[a[i]] += 1LL*a[i];
        l=min(l,a[i]); r=max(r,a[i]);
    }
    ++r;
    repi(k,l,r){
        dp[k+1][1] = dp[k][0]+scr[k];
        dp[k+1][0] = max(dp[k][0], dp[k][1]);
    }
    return max(dp[r][0], dp[r][1]);
}

void input(){
    scanf("%d", &n);
    rep(i,n) scanf("%d", a+i);
}

int main(){
    input();
    cout << solve() << endl;
    return 0;
}

Comments