动态规划dp

1.

思路：这是一个动态规划题目，核心思想就是当前数字为x这个数是取还是不取，如果取的话则前面那个数就不能取，如果不取的话则前面那个数可以取也可以不取，则就可以分成两种情况来讨论；

代码：

int dp[N]; 
int a[100005];
ll sum[100005],dp[100005][2];

scanf("%d",&n);
for(int i=1;i<=n;i++){
	scanf("%d",&a[i]);
	sum[a[i]]+=a[i];
}
for(int i=1;i<=100005;i++){
	dp[i][1]=dp[i-1][0]+sum[i];
	dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
}
printf("%lld",max(dp[100000][1],dp[100000][0]));