Codeforces 455A Boredom 取数字的dp

题目链接：点击打开链接

给定一个n长的序列

删除x这个数就能获得x * x的个数 的分数，然后x+1和x-1这2个数会消失。即无法获得这2个数的分数

问最高得分。

先统计每一个数出现的次数。然后dp一下，对于每一个数仅仅有取或不取2种状态。

#include <algorithm>

#include <cctype>

#include <cassert>

#include <cstdio>

#include <cstring>

#include <climits>

#include <vector>

#include<iostream>

#include <queue>

using namespace std;

#define ll long long

ll hehe;

#define N 100005

ll num[N], n;

ll dp[N][2];

void work(){

	for(ll i = 1; i < N; i++){

		dp[i][0] = max(dp[i-1][0], dp[i-1][1]);

		if(num[i]) {

			if(i-2>=0)

			dp[i][1] = max(dp[i-2][0], dp[i-2][1])+num[i]*i;

			dp[i][1] = max(dp[i][1], dp[i-1][0] + num[i]*i);

		}

	}

	cout<<max(dp[N-1][0], dp[N-1][1])<<endl;

}

int main(){

	ll i, j, u;

	while(cin>>n){

		memset(num, 0, sizeof num);

		memset(dp, 0, sizeof dp);

		for(i = 1; i <= n; i++)

		{

			scanf("%I64d", &u);

			num[u] ++;

		}

		work();

	}

    return 0;

}