P10229 [COCI 2023/2024 #4] Knjige 题解

知识点

前缀和、贪心、枚举。

题意分析

一个长度为 \(n\) 的单调不减的数列 \(\{ k_i \}\)，从左到右遍历，用 \(a\) 或 \(b\) 的代价，换 \(0\) 或 \(k_i\) 的价值。问：在总代价超过 \(t\) 之前，能够达到的最大价值为多少？

思路分析

显然是一个简单的决策题，但是即使简单，也要细细分析，找到做题的方法。

决策题，一般都是 DP 或贪心，看范围 \(10^9\) 就知道不太可能是 DP，那我们来尝试贪心。

由于数列 \(\{ k_i \}\) 单调不减，我们还被要求从左到右遍历，且每个数都要选择代价，明显能够知道尽量把后面的选了。

再来看该怎么选，我们可以直接从第一个开始枚举，这样我们就固定了选到的数的范围，剩下的只要判断合不合法、前缀和求解再更新答案即可。

CODE

#include<bits/stdc++.h>
#define ll long long
#define max(a,b) ((a)<(b)?(b):(a))
#define tomax(a,b) ((a)=max((a),(b)))
#define FOR(i,a,b) for(register int i=(a);i<=(b);++i)
#define main Main();signed main(){ios::sync_with_stdio(0);cin.tie(0);return Main();}signed Main
using namespace std;
constexpr int N=2e5+10;
int n,t,a,b;
ll ans,k[N];
signed main(){
	cin>>n>>t>>a>>b;
	FOR(i,1,n)cin>>k[i],k[i]+=k[i-1];
	FOR(i,1,n){
		if(b*i>t)break;
		tomax(ans,k[i]-k[max(0,i-(t-1ll*b*i)/(a-b))]);
	}cout<<ans<<endl;
	return 0;
}