有明显的递推关系:
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 int LL 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; }
Codeforces Round #260(div2)C(递推),布布扣,bubuko.com
Codeforces Round #260(div2)C(递推)
原文：http://www.cnblogs.com/zywscq/p/3916831.html