今天早上找一道题的bug,还是找不出来,下午刷了几道水题,晚上准备回家的事,
然后本来想打CF的,一看,数学场,不打了。
这道题的题意:
给出一个序列,每次你可以从这个序列里面选择一个数ak,删除,然后你的得分+ak,
代价是序列里面值为ak+1,ak-1的元素都删除
问:你能得到的最大得分是多少
思路:
你若删除了一个值为a的数,你的得分就是a*序列里面a的个数
因为a+1和a-1都被删除了,则其余的a不会被a+1,a-1这种情况删除了,你一定可以得到所有a的分数
所以这道题就是:在序列里面选择一些数值,你的得分+数值*该值出现的个数,并且,
数值+1和数值-1的数你就不能选了。
num[i]表示值i出现的次数。
_max表示出现的最大的值
dp[i][0]:表示从值1选择到i,如果不选择值i,可以得到的最大分数
dp[i][1]:表示从值1选择到值i,如果选择了值i,可以得到的最大分数。
注意:
1.这道题最后的结果要long long
2.小心中间过程溢出,我就是这个贡献了2个wa
3.CF的long long 要用cout输出
#include<cstdio>
#include<cstring>
#include<iostream> using namespace std;
#define LL long long
const int maxn=1e5+; inline LL max(LL x,LL y)
{
return x>y?x:y;
} int a[maxn];
LL dp[maxn][]; int main()
{
int n;
scanf("%d",&n);
int _max=-;
memset(a,,sizeof a);
for(int i=;i<=n;i++)
{
int u;
scanf("%d",&u);
a[u]++;
if(u>_max)
_max=u;
} memset(dp,,sizeof dp);
for(int i=;i<=_max;i++)
{
dp[i][]=dp[i-][]+(LL)a[i]*i;
dp[i][]=max(dp[i-][],dp[i-][]);
} cout<<max(dp[_max][],dp[_max][])<<endl; return ;
}