The Humanoid

Created by LXC on Thu Mar 7 15:18:45 2024

https://codeforces.com/problemset/problem/1759/E

ranting: 1500

tag: brute force, dp, sortings

problem

有 $n$ 名宇航员，他们每个人有大小为 $a_i$ 的能量。一个初始具有 $h$ 单位能量的邪恶的人形生物来这里吸收宇航员们的能量。

人型生物可以做以下三个动作：

• 吸收一个能量值严格低于当前人型生物的宇航员。
• 将自身的能量值翻倍 ($\times 2$), 这个操作最多能进行两次。
• 将自身的能量值翻三倍 ($\times 3$), 这个操作最多能进行一次。

其中，当一名具有 $a_i$ 能量的宇航员被吸收时，这名宇航员消失，人型生物的能量增加 $\lfloor {a_i\over 2} \rfloor$。

请你帮他算一算，如果他用最佳方案进行操作，他最多能吸收几名宇航员的能量？

第一行包含一个整数 $t\ (1\leq t \leq 10^4)$, 表示数据组数。

对于每组数据，第一行包含两个整数 $n\ (1\leq n \leq 2\cdot 10^5),h\ (1\leq h \leq 10^6)$, 分别代表宇航员人数和人形生物的初始能量。第二行包含 $n$ 个整数 $a_i\ (1\leq a_i \leq 10^8)$, 表示每名宇航员的能量。

保证 $\sum n\leq 2\cdot 10^5$。

对于每组数据，在单独的一行里输出一个整数，表示人形生物可以吸收宇航员的最大数量。

solution

$dp[i][j][k]$代表已经吸收了i个人的情况下，使用j瓶绿色药水，和k瓶蓝色药水，达到的最大力量。

如果$dp[i][j’][k’] * 2^{j-j’}*3^{k-k’} > a_i$，

$dp[i+1][j][k]$可以由$dp[i][j’][k’] * 2^{j-j’}*3^{k-k’}+\frac{a_i}{2}$决策最大值。维护合法dp状态$dp[i][j][k]$的最大的i为答案。

code

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

ll pw(int x, int y) {
    ll rt = 1;
    for (int i=0; i<x; i++) rt *= 2;
    for (int i=0; i<y; i++) rt *= 3;
    return rt;
}

void sol() {
    ll n, h;
    cin >> n >> h;
    vector<ll> a(n);
    for (auto& i:a) cin >> i;
    sort(a.begin(), a.end());
    ll f[n+1][3][2];
    memset(f, -1, sizeof(f));
    for (int i=0; i<=2; i++) {
        for (int j=0; j<=1; j++) {
            f[0][i][j] = h*pw(i,j);
        }
    }
    int ans = 0;
    for (int i=0; i<n; i++) {
        for (int g=0; g<=2; g++) {
            for (int b=0; b<=1; b++) {
                if (f[i][g][b] == -1) continue;
                for (int rg=g; rg<=2; rg++) {
                    for (int rb=b; rb<=1; rb++) {
                        if (f[i][g][b]*pw(rg-g, rb-b) > a[i]) {
                            ans = i+1;
                            f[i+1][rg][rb] = max(f[i][g][b]*pw(rg-g, rb-b)+a[i]/2, f[i+1][rg][rb]);
                        }    
                    }
                }
            }
        }
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}