codeforces 456 C. Boredom

http://codeforces.com/contest/456/problem/C
题意:给出n(1E5)个数(1E5),每次可以选一个数a[k]并删掉a[k],a[k]-1,a[k]+1得到a[k]分,问最多能得到的分数。
思路:裸dp.f[i]表示选到数i的时候能达到的最大分数。开一个计数数组cnt[x]表示数字x出现的次数。那么显然有f[0]=0,f[1]=cnt[1],f[i(i>=2)] = max(f[i-1],f[i-2]+f[i]*cnt[i]);答案为f[max(a[i])],注意要开long long

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz