The 2024 Shanghai Collegiate Programming Contest K. 时光

思路讲解

就是注意到那，这个如果确定了要面对什么经历，那么肯定是选择从大到小经历最好，现在的问题就在于怎么样求这个东西，以及怎么拼起来？

那么拼起来我们用的是cal函数，其会调用mp解决拼起来的问题。

// 其实逻辑是先搞后一半，因为公式是sumB1*k2+val2+val1，那么我们要最大化sumB1*k2+val2
// 直接搞最大化比较难，但是k比较小，可以记录不同k下的val，最大化这个val。

// 输入剩余值 和 总经历数 返回最大的sumB1*k2+val2
auto cal=[&](ll rem,ll sumB1)->ll{
	ll res=0;
	for(int i=1;i<=N;++i){
		auto it=lower_bound(mp[i].begin(),mp[i].end(),(array<ll,2>){rem,INF});
		if(it==mp[i].begin()){
			continue;
		}
		it=prev(it);
		ll val2=(*it)[1];
		res=max(sumB1*i+val2,res);
	}
	return res;
};

AC代码

https://codeforces.com/gym/105229/my#

源代码

#include <bits/stdc++.h>
#define debug(x) cerr<<#x<<":"<<x<<"\n";

using namespace std;

using  ll = long long;
const ll INF=(ll)1e17+3;
/*

*/
inline void solve(){
	ll N,M;
	cin>>N>>M;
	vector<array<ll,2> > ab(N+5,{0,0});
	for(int i=1;i<=N;++i){
		cin>>ab[i][0];
	}
	for(int i=1;i<=N;++i){
		cin>>ab[i][1];
	}
	sort(ab.begin()+1,ab.begin()+N+1,[](array<ll,2> a,array<ll,2> b){return a[1]>b[1];});
	
	ll half=N/2;ll halfs=N-half;
	vector<vector<array<ll,2> > > mp(N+5);
	ll Ans=0;
	// 先处理后半部分
	for(int i=0;i<=(1<<halfs);++i){
		bitset<30> bi(i);
		ll lans=0,sum=0,cnt=0,cost=0;
		for(int j=0;j<=halfs-1;++j){
			ll idx=j+half+1,b=ab[idx][1],a=ab[idx][0];
			if(bi[j]){
				cost+=a;
				lans+=sum;
				sum+=b;
				++cnt;
			}
		}
		if(cost>M) continue;
		Ans=max(Ans,lans);
		mp[cnt].push_back({cost,lans});
	}
	for(int i=1;i<=N;++i){
		sort(mp[i].begin(),mp[i].end());
	}
	for(int i=1;i<=N;++i){
		if(mp[i].empty()) continue;
		ll mx=0;
		for(int j=0;j<(int)mp[i].size();++j){
			mx=max(mx,mp[i][j][1]);
			mp[i][j][1]=mx;
		}
	}
	// 输入剩余值 和 总经历数 返回最大的sumB1*k2+val2
	auto cal=[&](ll rem,ll sumB1)->ll{
		ll res=0;
		for(int i=1;i<=N;++i){
			auto it=upper_bound(mp[i].begin(),mp[i].end(),(array<ll,2>){rem,INF});
			if(it==mp[i].begin()){
				continue;
			}
			it=prev(it);
			ll val2=(*it)[1];
			res=max(sumB1*i+val2,res);
		}
		return res;
	};
	// 处理前半部分
	for(int i=0;i<=(1<<half);++i){
		bitset<30> bi(i);
		ll lans=0,sum=0,cnt=0,cost=0;
		for(int j=0;j<=half-1;++j){
			ll idx=j+1,b=ab[idx][1],a=ab[idx][0];
			if(bi[j]){
				cost+=a;
				lans+=sum;
				sum+=b;
				++cnt;
			}
		}
		if(cost>M) continue;
		Ans=max(Ans,lans+cal(M-cost,sum));
	}
	cout<<Ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// ll lT;
	// cin>>lT;
	// while(lT--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://codeforces.com/gym/105229/my#
326774018
*/

心路历程（WA，TLE，MLE……）