<题目链接>
题目大意：
给定一个序列，让你在其中挑选一些数，如果你选了x,那么你能够得到x分，但是该序列中所有等于x-1和x+1的元素将全部消失，问你最多能够得多少分。
解题分析：
从小到大枚举选的数的数值，同时用DP进行状态的转移，$dp[i]$表示前 $i$ 的数值中，挑选$i$的最大得分。
所以不难得到dp的转移方程为:$$dp[i]=max(dp[i-1],dp[i-2]+num[i]*i)$$
#include <bits/stdc++.h> using namespace std; const int N = 1e5+5; typedef long long ll; int n; ll num[N],dp[N]; int main(){ scanf("%d",&n); int mx=-1e9,mn=1e9; for(int i=1;i<=n;i++){ int now;scanf("%d",&now); num[now]++; mx=max(mx,now); mn=min(mn,now); } for(int i=mn;i<=mx;i++){ if(i==1){ dp[i]=max(dp[i-1],num[i]*i); }else{ dp[i]=max(dp[i-1],dp[i-2]+num[i]*i); //选数值为i-1的数 和 选数值为i的数 的状态转移方程 } } printf("%lld\n",dp[mx]); }
Codeforces 455A Boredom (线性DP)
原文：https://www.cnblogs.com/00isok/p/10635723.html