CodeForces - 456C Boredom(线性dp)

题目链接：点击查看

题目大意：给出一个由n个数字组成的数列，现在给出规则是，每次选择数列中的一种数字 x，选择后的贡献为 x，不过操作后会删除掉所有数值为 x + 1 和 x - 1 的数，现在问如何选择可以使得贡献最大

题目分析：线性dp，因为每个数若选择的话，那么他前后两个数都无法选择了，我们可以直接视为相邻两个数的关系，若当前的数选了，那么前一个数就没法选，若当前的数不选，则前一个数是可以选的，虽然这样无法限制到后面的那个数，但是随着状态的转移，到达后一个数时的决策和前面的决策并不会冲突，所以dp[i]代表选择数字 i 的最大贡献，那么转移方程就是：

dp[i]=max(dp[i-1],dp[i-2]+num*cnt[num])，i代表的是数值，范围为[1,1e5]

cnt数组是每个数字出现的次数，维护好所需要的信息后，直接转移就好了

代码：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<cmath> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;int cnt[N];LL dp[N];int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n;scanf("%d",&n);for(int i=1;i<=n;i++){int num;scanf("%d",&num);cnt[num]++;}LL ans=0;dp[1]=cnt[1];for(int i=1;i<N;i++){dp[i]=max(dp[i-2]+1LL*i*cnt[i],dp[i-1]);ans=max(ans,dp[i]);}printf("%lld\n",ans);return 0; }

 

总结

以上是生活随笔为你收集整理的CodeForces - 456C Boredom(线性dp)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。