牛客小白月赛30 J.小游戏 (DP)

题意:给你一组数,每次可以选择拿走第\(i\)个数,得到\(a[i]\)的分数,然后对于分数值为\(a[i]-1\)和\(a[i]+1\)的值就会变得不可取,问能得到的最大分数是多少.
题解:\(a[i]\)最大取\(2e5\),那我们可以枚举\([1,2e5]\)的所有数字,用桶记录每个数出现的次数\(cnt[x]\),对于当前所枚举的数\(x\),我们有两种选择:

1.选

2.不选

假如我们选择\(x\),那么\(x-1\)肯定不能选的,不难想,最优的情况一定是从最近的\(x-2\)转移过来并且加上当前的贡献,假如我们不选的话,那么我们的状态就应该从上一个数\(x-1\)转移过来,所以状态转移方程就是\(dp[i]=max(dp[i-1],dp[i-2]+i*cnt[i])\).

代码:

#include <bits/stdc++.h>

#define ll long long

#define fi first

#define se second

#define pb push_back

#define me memset

#define rep(a,b,c) for(int a=b;a<=c;++a)

#define per(a,b,c) for(int a=b;a>=c;--a)

const int N = 1e6 + 10;

const int mod = 1e9 + 7;

const int INF = 0x3f3f3f3f;

using namespace std;

typedef pair<int,int> PII;

typedef pair<ll,ll> PLL;

ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}

ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}

int n;

int cnt[N];

ll dp[N];

ll ans=0;

int main() {

    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	cin>>n;

	rep(i,1,n){

		int x;

		cin>>x;

		cnt[x]++;

	}

	dp[1]=max(0,cnt[1]);

	rep(i,0,200010){

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

		ans=max(ans,dp[i]);

	}

	cout<<ans<<'\n';

    return 0;

}

巴特西

牛客小白月赛30 J.小游戏 (DP)

最新文章

热门文章