CCF CAT

xqy2003 / 2023-07-03 / 原文

题面

Best Travel Plans

枚举在哪个城市停止旅行 , 这样我们在路程上花费的时间就确定了 , 同时确定了在活动上花费的时间

对于活动花费的时间，我们贪心选择每一秒的最优值即可

#include <bits/stdc++.h>
using ll = long long;

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	
	int n,m;
	std::cin >> n >> m;
	
	std::vector<int> t(n + 1) , e(n + 1) , d(n + 1);
	
	for(int i = 2 ; i <= n ; ++i)
		std::cin >> t[i];
	for(int i = 1 ; i <= n ; ++i)
		std::cin >> e[i];
	for(int i = 1 ; i <= n ; ++i)
		std::cin >> d[i];
		
	std::vector<std::vector<int>> p(n + 1);
	
	for(int i = 1 ; i <= n ; ++i) {
		for(int j = 0 ; e[i] - j * d[i] > 0 && j <= m; ++j) {
			p[i].emplace_back(e[i] - j * d[i]);
		}	
	}
	
	int travel = 0 , ans = 0;
	for(int i = 1 ; i <= n ; ++i) { //枚举在哪座城市停止旅行 
		
		travel += t[i];
		int remain = m - travel;
		if(remain <= 0) break;
		
		std::vector<int> pos(n + 1 , 0);
		
		int sum = 0;
		for(int j = 1 ; j <= remain ; ++j) { //枚举每一秒时间怎么用 
			int mx = 0 , id ;
			for(int k = 1 ; k <= i ; ++k) {
				if(pos[k] > p[k].size() - 1) continue;
				if(p[k][pos[k]] > mx) {
					mx = p[k][pos[k]] , id = k;
				}
			}
			sum += mx , pos[id]++; //每一个城市的活动都需要连续地接上
		}
		
		ans = std::max(ans , sum);
			
	}
	
	std::cout << ans << '\n';
	
	return 0;
}