【朴素DP】CF834div3 E. The Humanoid

Myth丶恋晨 2024-03-22 10:07 58阅读 0赞

**虽然是简单DP，但是不妨碍我不会**

[Problem - E - Codeforces][]

![a8cd5785c72547d59250f8894080b693.png][]

思路：

设dp\[i\]\[j\]\[k\]为前i个人，第一种药剂选了j个，第二种药剂选了k个的最大等级

然后答案就是从n到1枚举，找出最大符合条件的

转移的时候就是考虑喝不喝那几瓶药的那几种决策来转移

Code：

#include <iostream>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    #include <set>
    #include <vector>
    #include <cmath>
    #include <map>
    #include <unordered_map>
    
    using namespace std;
    #define int long long
    #define NO {puts("NO") ; return ;}
    #define YES {puts("YES") ; return ;}
    #define please return 
    #define ac 0
    typedef pair<int, int> PII;
    const int N = 2e5 + 10 , INF = 0x3f3f3f3f;
    int n, m, k, a[N];
    int f[N][5][5];
    int ans[N];
    
    void solve()
    {   
        cin >> n >> k;
        for(int i = 1; i <= n ; i++ ) {
            cin >> a[i];
            ans[i] = -INF;
            for(int j = 0; j < 3; j++ )
                for(int l = 0; l < 2; l++) 
                    f[i][j][l] = -INF;
        }
        sort(a + 1, a + n + 1);
        
        f[0][2][1] = k;
        f[0][1][0] = k * 6;
        f[0][0][0] = k * 12;
        f[0][0][1] = k * 4;
        f[0][1][1] = k * 2;
        f[0][2][0] = k * 3;
        
        for(int i = 1; i <= n ; i++ ) {
            for(int j = 0; j < 3; j++ )
                for(int l = 0; l < 2; l++) {
                    if(f[i - 1][j][l] > a[i]) {
                        f[i][j][l] = max(f[i][j][l], f[i - 1][j][l] + a[i] / 2);
                    }
                }
            for(int j = 0; j < 3; j++ )
                for(int l = 0; l < 2; l++) {
                    if(j >= 2 && l >= 1) f[i][j - 2][l - 1] = max(f[i][j - 2][l - 1], f[i][j][l] * 12); // 2 1
                    if(j >= 2)           f[i][j - 2][l] =     max(f[i][j - 2][l],     f[i][j][l] * 4); // 2 0
                    if(j >= 1 && l >= 1) f[i][j - 1][l - 1] = max(f[i][j - 1][l - 1], f[i][j][l] * 6); // 1 1
                    if(j)                f[i][j - 1][l] =     max(f[i][j - 1][l],     f[i][j][l] * 2);     // 1 0
                    if(l)                f[i][j][l - 1] =     max(f[i][j][l - 1],     f[i][j][l] * 3);     // 0 1
                }
            // for(int j = 0; j < 3; j++ )
            //     for(int l = 0; l < 2; l++) {
            //         cout << f[i][j][l] << " ";
            //     }
            // cout << endl;
        }
        for (int i = 1; i <= n; i++ ) {
            for(int j = 0; j < 3; j++ )
                for(int l = 0; l < 2; l++) {
                    ans[i] = max(ans[i], f[i][j][l]);
                }
        }
        //for(int i = 1; i <= n ; i ++ ) cout << ans[i] << " "; cout << endl;
        for(int i = n ; i >= 1; i -- ) {
            if(ans[i] - a[i] / 2 > a[i]) {
                cout << i << endl;
                return ;
            }
        }
        cout << 0 << endl;
    }
    
    signed main()
    {
        ios::sync_with_stdio(0),cin.tie(0);
        // freopen("input.txt", "r", stdin);
        int T = 1;
        cin >> T;
        while(T -- ) solve();
        please ac;
    }

[Problem - E - Codeforces]: https://codeforces.com/contest/1759/problem/E
[a8cd5785c72547d59250f8894080b693.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/1f21b6b2b4c14433882b0394b677f5df.png