无脑尝试
脑子有坑,勿理
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
// #pragma GCC optimize(2)
// #pragma GCC optimize(3)
#define IOS std::ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define int long long
#define x first
#define y second
#define cmp [&](PII a, PII b){return a.y < b.y;}
const int N = 5e5+10, mod = 1e9+7, M = 5e7+5, K = 2e5+10, Z = 1e5+7, X = 3e5+3;
using namespace std;
typedef long long LL;
typedef priority_queue<int> PQI;
typedef priority_queue <int, vector<int>, greater<>> PQGI;
typedef pair<int, int> PII;
int a[Z], sum1, sum2, sum;
void solve()
{
int n; cin >> n;
for(int i = 1; i <= n; i ++)
{
int x; cin >> x;
a[x] ++;
}
for(int i = 100000; i >= 1; i -= 2)
sum1 = sum1 + a[i] * i;
for(int i = 99999; i >= 1; i -= 2)
sum2 = sum2 + a[i] * i;
for(int i = 3; i >= 1; i --)
{
if(a[i] * i >= (a[i - 1] * (i - 1) + a[i + 1] * (i + 1)))
{
sum = sum + a[i] * i, i -= 2;
// a[i - 1] = 0, a[i + 1] = 0, i --;
}
}
cout << max(max(sum1, sum2), sum) << endl;
return;
}
signed main()
{
IOS; int T = 1;
cin.tie(nullptr);
cout.tie(nullptr);
// cin >> T;
while( T -- ) solve();
return 0;
}
AC code
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
// #pragma GCC optimize(2)
// #pragma GCC optimize(3)
#define IOS std::ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define int long long
#define x first
#define y second
#define cmp [&](PII a, PII b){return a.y < b.y;}
const int N = 5e5+10, mod = 1e9+7, M = 5e7+5, K = 2e5+10, Z = 1e5+7, X = 3e5+3;
using namespace std;
typedef long long LL;
typedef priority_queue<int> PQI;
typedef priority_queue <int, vector<int>, greater<>> PQGI;
typedef pair<int, int> PII;
int a[Z], dp[Z];
void solve()
{
int n; cin >> n;
for(int i = 1; i <= n; i ++)
{
int x; cin >> x;
a[x] += x;
}
for(int i = 1; i <= 100000; i ++)
dp[i] = max(dp[i - 1], dp[max(0LL, i - 2)] + a[i]);
cout << dp[100000] << endl;
}
signed main()
{
IOS; int T = 1;
cin.tie(nullptr);
cout.tie(nullptr);
// cin >> T;
while( T -- ) solve();
return 0;
}