Codeforces 455A Boredom (线性DP)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

<题目链接>

题目大意：
给定一个序列，让你在其中挑选一些数，如果你选了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+;
typedef long long ll;
int n;
ll num[N],dp[N];int main(){
scanf("%d",&n);
int mx=-1e9,mn=1e9;
for(int i=;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==){
dp[i]=max(dp[i-],num[i]*i);
}else{
dp[i]=max(dp[i-],dp[i-]+num[i]*i); //选数值为i-1的数和选数值为i的数的状态转移方程
}
}
printf("%lld\n",dp[mx]);
}