首页 > 代码库 > Codeforces Round #260(div2)C(递推)

Codeforces Round #260(div2)C(递推)

2024-07-17 23:01:16   218人阅读

有明显的递推关系:

f[i]表示i为数列中最大值时所求结果。num[i]表示数i在数列中出现了几次。

对于数i，要么删i，要么删i-1,只有这两种情况，且子问题还是一样的思路。那么很显然递推一下就行了：f[i]=max(f[i-1],f[i-2]+i*num[i]);

这里技巧在于：为了防止麻烦，干脆就所有数的出现次数都记录一下，然后直接从2推到100000（类似于下标排序），就不用排序了，也不用模拟删除操作了。这一技巧貌似简单，但实际上临场想出来也需要点水平。

#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<map>#include<set>#include<vector>#include<algorithm>#include<stack>#include<queue>using namespace std;#define INF 1000000000#define eps 1e-8#define pii pair<int,int>#define LL long long intLL f[100005],num[100005];int n,x;int main(){    //freopen("in3.txt","r",stdin);    //freopen("out.txt","w",stdout);    scanf("%d",&n);    for(int i=1;i<=n;i++)    {        scanf("%d",&x);        num[x]++;    }    f[1]=num[1];f[0]=0;    for(LL i=2;i<=100000;i++)    {        f[i]=max(f[i-1],f[i-2]+i*num[i]);    }    printf("%I64d\n",f[100000]);    //fclose(stdin);    //fclose(stdout);    return 0;}

 


联系
我们