F智乃的算法竞赛群友（完全背包DP+贪心）

想用背包DP，但发现n规模达到1e9。

考虑对n >= upper的部分直接用性价比最高的，n < upper的范围再进行完全背包DP。upper可以人为设定，但最好不要超过1000，因为题目未限定T个测试样例的n的和，所以可能每个样例的n都超过upper，导致超时。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f3f3f;
const int upper = 499;

void solve() {
    ll n, a, b; cin>>n>>a>>b;
    vector<ll> cost = {0, 7, 8, 2};
    vector<ll> val = {0, a, a+b, b};
    if (n <= upper) {
        vector<ll> dp(n+1, 0);
        for (int i=1; i<=3; i++) {
            for (ll j=cost[i]; j<=n; j++) {
                dp[j] = max(dp[j], dp[j-cost[i]] + val[i]);
            }
        }
        cout<<dp[n]<<'\n';
        return ;
    }
    //n > upper
    //1
    ll res = 0;
    ll fcost = -1, fval = -1;
    if (8*a >= 7*(a+b) && 2*a >= 7*b) {
        fcost = cost[1]; fval = val[1];
    }
    else if (7*(a+b) >= 8*a && 2*(a+b) >= 8*b) {
        fcost = cost[2]; fval = val[2];
    }
    else {
        fcost = cost[3]; fval = val[3];
    }
    ll tmp = (n-upper) / fcost;
    res = tmp * fval;
    n -= tmp * fcost;
    vector<ll> dp(n+1, 0);
    for (int i=1; i<=3; i++) {
        for (ll j=cost[i]; j<=n; j++) {
            dp[j] = max(dp[j], dp[j-cost[i]] + val[i]);
        }
    }
    res += dp[n];
    cout<<res<<'\n';
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int T; cin>>T;
    while (T--) solve();

    return 0;
}