递推DP Codeforces Round #260 (Div. 1) A. Boredom

题目传送门

 /*
DP:从1到最大值,dp[i][1/0] 选或不选,递推更新最大值
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std; typedef long long ll;
const int MAXN = 1e5 + ;
const int INF = 0x3f3f3f3f;
ll dp[MAXN][];
ll cnt[MAXN]; ll work(int mx)
{
ll ret = ;
for (int i=; i<=mx; ++i)
{
dp[i][] = dp[i-][] + cnt[i] * i;
dp[i][] = max (dp[i-][], dp[i-][]);
ret = max (ret, dp[i][]);
ret = max (ret, dp[i][]);
} return ret;
} int main(void) //Codeforces Round #260 (Div. 1) A. Boredom
{
int n; scanf ("%d", &n); int mx = ;
for (int i=; i<=n; ++i)
{
int x; scanf ("%d", &x); cnt[x]++;
mx = max (mx, x);
} printf ("%I64d\n", work (mx)); return ;
}
上一篇:wifi配置参数


下一篇:Zabbix 监控tomcat web