12pts,就第一个点AC,求hack
查看原帖
12pts,就第一个点AC,求hack
240497
Cha_楼主2024/8/29 09:18
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 7;
int n,k;
int a[MAXN];
int dp[MAXN][2];//dp[i][0/1]表示分小于 i 的人上线; dp[i][0]表示 i 分不上线最大,dp[i][1]表示 i 分上线最大,
int max_score = -1,num;
int main(){
	cin >> n >> k;
	for(int i = 1;i <= n;i++){
		int tmp;
		cin >> tmp;
		if(a[tmp] == 0){
			num++;
		}
		a[tmp]++;
		max_score = max(max_score,tmp);
	}
	if(k == 0){
		cout << num;
		return 0;
	}
	int sum = 0;
	dp[0][0] = 0;
	dp[0][1] = a[0];
	for(int i = 1;i <= max_score;i++){
		if(i >= k){
			dp[i][1] = a[i] + dp[i - k][0];
		}else{
			dp[i][1] = a[i] + max(dp[i - 1][1],dp[i - 1][0]);
		}
		dp[i][0] = max(dp[i - 1][1],dp[i - 1][0]);
	}
	cout << max(dp[max_score][1],dp[max_score][0]);
	return 0;
}
2024/8/29 09:18
加载中...