这道题目……题意应该比较好懂,就是给出一个序列,每次可以删除一个数,然后得到相当于这个数大小的得分,同时与此数相差1的所有数也会被删去。
问能够得到的最大得分。
显然序列中数的顺序是不影响结果的,又因为在删除每一个数时与其关联的是相邻的数。比较容易可以想到DP的做法,用类似桶排的方法把数先后顺序确定,再从前往后推,这样考虑第i个数是否删去时只用考虑前一个相邻的数的情况即可。
先预处理出b[i]为大小为i的数总共可得的得分。(因为删去某数后,和其同样大小的数之后删除时没有任何代价,所以可以看做一起删去)同时在预处理时记录下序列中最大的数m。然后,我们记f[i][1]为对于序列中1-i的所有数,选中大小为i的所有数时可得的最大得分,f[i][0]即为不选i时候的情况。从前往后递推即可。最后输出max(f[m][0],f[m][1])。
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<vector> #include<string> #include<set> #include<queue> #include<stack> #include<map> #include<cmath> #include<cstdlib> #define ll long long #define maxn 100010 #define inf 1000000000 #define linf (1LL<<50) using namespace std; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x*=10;x+=ch-'0';ch=getchar();} return x*f; } inline void read(char *s,int &ts) { char x=getchar(); while(!(x>='a'&&x<='z'))x=getchar(); while(x>='a'&&x<='z')s[++ts]=x,x=getchar(); } ll n,m,a[maxn],f[maxn][2]; int main() { scanf("%I64d",&n); for(int i=1;i<=n;i++) { ll x; scanf("%I64d",&x); a[x]+=x; m=max(m,x); } for(int i=1;i<=m;i++) { f[i][0]=max(f[i-1][0],f[i-1][1]); f[i][1]=f[i-1][0]+a[i]; } printf("%I64d\n",max(f[m][0],f[m][1])); return 0; }