2025 United Kingdom and Ireland Programming Contest (UKIEPC 2025) 2025 英国 ICPC——G. Get Good

题目大意

题目总结：G. Get Good

基本参数

• $n$: 总天数。

• $a$: 处于“精力充沛”状态下每日获得的技能点。

• $b$: 处于“疲劳”状态下每日获得的技能点（$a \ge b$）。

• $x$: 连续工作 $x$ 天后，状态从“精力充沛”转为“疲劳”。

• $y$: 连续休息 $y$ 天后，状态重置为“精力充沛”。

规则说明

1. 初始状态：第 1 天开始时处于“精力充沛”状态。

2. 工作机制：

• 前 $x$ 天工作，每天得 $a$ 分。
• 从第 $x+1$ 天起如果不休息继续工作，每天得 $b$ 分。

1. 休息机制：随时可以开始连续休息 $y$ 天。休息期间得 0 分，休息结束后重新变为“精力充沛”状态（即又能享受 $x$ 天的高收益 $a$）。

2. 目标：在 $n$ 天内通过合理安排工作与休息的时间，求最大化技能点总和。

---

样例解释

• 样例 2 ($n=4, a=4, b=2, x=3, y=3$)

  • 方案 A：连续工作 4 天。前 3 天得 $3 \times 4 = 12$，第 4 天疲劳得 2，总分 $12+2=14$。
  • 方案 B：工作 1 天后休息 3 天。总分 4。
  • 最大值：14。

• 样例 3 ($n=5, a=3, b=2, x=3, y=1$)

  • 方案 A：工作 5 天。前 3 天得 $3 \times 3 = 9$，后 2 天疲劳得 $2 \times 2 = 4$，总分 13。
  • 方案 B：工作 3 天（得 9），休息 1 天，第 5 天重新精力充沛工作（得 3），总分 $9+0+3=12$。
  • 最大值：13。

• 样例 4 ($n=5, a=4, b=1, x=3, y=1$)

  • 由于疲劳收益 $b=1$ 太低，休息 1 天比疲劳工作更划算。
  • 方案：工作 3 天（得 $3 \times 4 = 12$），休息 1 天（得 0），第 5 天重新开始工作（得 4），总分 $12+0+4=16$。
  • 最大值：16。

思路讲解

ll N,a_fresh,b_tired,x_do,y_rest;
cin >> N>>a_fresh>>b_tired>>x_do>>y_rest;
// if (a_fresh==b_tired) {
//     cout<<N*a_fresh<<"\n";
//     return;
// }
ll l=N*b_tired,r=N*a_fresh;
ll ans=0;
do {
    ll num_a=min(x_do,N),num_b=N-num_a;
    ll lans=num_a*a_fresh+num_b*b_tired;
    ans=max(lans,ans);
}while (false);
do {
    ll num_a=N/(x_do+y_rest),rem=N-num_a*(x_do+y_rest);
    ll lans=num_a*x_do*a_fresh+min(rem,x_do)*a_fresh+
        (rem-min(rem,x_do))*b_tired;
    ans=max(lans,ans);
}while (false);
// 最后一段加上的原因见下：
do {
    ll num_a=N/(x_do+y_rest);
    ll rem=0;
    if (num_a>=1) {
        rem=N-num_a*(x_do+y_rest);
        rem+=y_rest;
    }else {
        rem=N-num_a*(x_do+y_rest);
    }
    ll lans=num_a*x_do*a_fresh+rem*b_tired;
    ans=max(lans,ans);
}while (false);
cout<<ans<<"\n";

b 和 a，x 的不同关系已经在前两种情况中包含了，但是 b 和 x+a+x 的关系还没有包含。

AC代码

源代码

/**
 * Problem: G. Get Good
 * Contest: 2025 United Kingdom and Ireland Programming Contest (UKIEPC 2025)
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106157/problem/G
 * Created: 2026-02-06 12:20:41
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */

void Solve() {
    ll N,a_fresh,b_tired,x_do,y_rest;
    cin >> N>>a_fresh>>b_tired>>x_do>>y_rest;
    // if (a_fresh==b_tired) {
    //     cout<<N*a_fresh<<"\n";
    //     return;
    // }
    ll l=N*b_tired,r=N*a_fresh;
    ll ans=0;
    do {
        ll num_a=min(x_do,N),num_b=N-num_a;
        ll lans=num_a*a_fresh+num_b*b_tired;
        ans=max(lans,ans);
    }while (false);
    do {
        ll num_a=N/(x_do+y_rest),rem=N-num_a*(x_do+y_rest);
        ll lans=num_a*x_do*a_fresh+min(rem,x_do)*a_fresh+
            (rem-min(rem,x_do))*b_tired;
        ans=max(lans,ans);
    }while (false);
    do {
        ll num_a=N/(x_do+y_rest);
        ll rem=0;
        if (num_a>=1) {
            rem=N-num_a*(x_do+y_rest);
            rem+=y_rest;
        }else {
            rem=N-num_a*(x_do+y_rest);
        }
        ll lans=num_a*x_do*a_fresh+rem*b_tired;
        ans=max(lans,ans);
    }while (false);
    // if (a_fresh*x_do/(double)(x_do+y_rest)>b_tired/(double)(x_do+y_rest)) {
    //
    // }
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/gym/106157/submission/361663845
AC
https://qoj.ac/submission/2009999
1
4 4 2 3 3

1
2 2 2 2 2

*/

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