题解归档 - cf455A

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf455A
• 本地来源：problems/cf455A/idea.md
• 题目链接：https://codeforces.com/contest/455/problem/A
• 原始标题：455A Boredom

思路

455A Boredom

题意

给定长度 (n) 的序列 (a_i\in[1,10^5])。一步可选某个值 (k)，删除序列中所有等于 (k,k-1,k+1) 的元素，获得 (k) 分（每个被删的 (k) 贡献 (k) 分）。求最大总分。

思路

操作等价于：在值域上选若干互不相邻的整数 (v)，得分 (\sum v\cdot cnt[v])，其中 (cnt[v]) 为 (v) 出现次数。

先统计频次，再 DP（打家劫舍）：

[
dp[i]=\max\bigl(dp[i-1],\; dp[i-2]+cnt[i]\cdot i\bigr)
]

边界：(dp[0]=0)，(dp[1]=cnt[1])。答案 (dp[\max a_i])。

注意：Catalog 标注 sqrt decomposition，但本题标准解是值域 DP，与分块无关；分块模板另见 lib/数据结构(分块).cpp。

实现要点

• 循环从 (i=2) 开始，避免 (i=1) 时访问 dp[-1]。
• 值域上界 (10^5)，cnt/dp 开全局数组即可。

复杂度

• 时间：(O(n + V))，(V=10^5)
• 空间：(O(V))

验证

• 样例：✅（输出 10）
• 对拍：stress.py cf455A -n 500（(n\le15)，值域 (\le8)）

结果

• CF 提交 #377697332 — AC
• 模板已沉淀：lib/数据结构(分块).cpp（Catalog 缺口；本题本身为 DP，分块见同场 455D）

代码

来源：problems/cf455A/solution.cpp

/* Author: likely
 * Time: 2026-06-08 02:42:15
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=1e5;
ll cnt[maxn+5],p[maxn+5],dp[maxn+5],n,i,k,tot;
int main(){
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>k;
        cnt[k]++;
    }
    for(i=1;i<=maxn;i++) if(cnt[i]) p[++tot]=i;
    if(!tot){
        cout<<0<<"\n";
        return 0;
    }
    dp[1]=cnt[p[1]]*p[1];
    for(i=2;i<=tot;i++){
        if(p[i]==p[i-1]+1) dp[i]=max(dp[i-1],dp[i-2]+cnt[p[i]]*p[i]);
        else dp[i]=dp[i-1]+cnt[p[i]]*p[i];
    }
    cout<<dp[tot]<<"\n";
    return 0;
}