Preface

😕 👀️

（NaHCO3：

我们要严厉表扬这种使用AI写标程并且使用标程生成代码并且不做对拍的行为。） 我在此向所有同学道歉，出了道错题…… (其实这题不看样例还是可以做的）

题意

Tap能使你收获 a 的连击数，但是会耗费你 A 的精力和一根手指。

Hold能使你收获 b 的连击数，但是会耗费你 B 的精力和一根手指。

Flick能使你收获 c 的连击数，但是会耗费你 C 的精力和一根手指。

Drag能使你收获 d 的连击数，但是会耗费你 D 的精力和一根手指。

由于小Q同时最多只能使用4根手指，并且他的精力有限，只有 w 。一旦他的精力耗尽，他就会「Track Lost」，并且骂骂咧咧地退出游戏。

小Q想要知道，在不耗光他的精力的前提下，他最多能获得多少「​连击​」数和在获得最多连击数的情况下最多能完全抵挡多少次攻击（攻击定义见输入）。由于答案可能很大，请你对 $10^9+7$ 取模。 （请注意，一旦小Q没有接到某次攻击的任何一个道具，「​连击​」数就会清零）

思路

考虑使用动态规划，实际上是状压dp

（因为这题长得很像多重背包！）

• dp[i][j] 表示处理完第 i 波攻击后，剩余精力为 j 时的最大连击数。

• 对于每一波攻击，先计算当前波中每个道具的实际精力消耗 cur_w 和连击数 cur_v。

• 枚举使用手指的数量 use（最多 4 个），使用位运算生成使用 use 个道具的所有组合（通过 mask，见代码）。

• 计算每种组合的精力消耗 cur_w_sum 和连击数 cur_v_sum，并更新 dp 数组。

• 计算最多能抵挡的攻击次数：

  • 从最后一波开始向前遍历，同样枚举使用手指的数量和道具组合，找到能让当前 dp 值等于上一波 dp 值加上当前组合连击数的情况，更新能量并增加抵挡攻击次数 cur_attack。

时间复杂度

• ​动态规划部分​：
  • 外层循环遍历 m 波攻击，对于每一波攻击，内层循环枚举使用手指的数量，最多为 4 次，然后生成道具组合的时间复杂度是 O($2^k$)，计算每种组合的属性的时间复杂度是O(k) ，更新 dp 数组的时间复杂度是 O($w$)。
• ​计算最多能抵挡的攻击次数部分​：
  • 从最后一波开始向前遍历，时间复杂度为O(m) ，对于每一波攻击，枚举使用手指的数量和道具组合的时间复杂度与动态规划部分相似，约为O($2^k*k$) 。
  • 总的时间复杂度为 O($m*k*2^k*w$)。

标程

#include<bits/stdc++.h>
#define int long long
#define inf 1e18
#define mod 1000000007
using namespace std;

int read()
{
    char c=getchar();
    int f=1,k=0;
    while(c<'0'||c>'9')
    {
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        k*=10;
        k+=c-'0';
        c=getchar();
    }
    return k*f;
}

string readStr()
{
    string s = "";
    char c = getchar();
    while(c == ' ' || c == '\n') c = getchar();
    while(c!= ' ' && c!= '\n')
    {
        s += c;
        c = getchar();
    }
    return s;
}
 /* readStr ​：
  * 功能：从标准输入读取一个字符串，
跳过空格和换行符。
  * 实现：使用 `getchar` 函数逐字符读取，
拼接字符直到遇到空格或换行符。*/

void write(int k)
{
    if(k<0)
    {
        putchar('-');
        k=-k;
    }
    if(k<10) putchar(k+'0');
    else write(k/10),putchar(k%10+'0');
    return;
}

int n,m,k,ww;
int a[1000005];
int v[1000005],w[1000005];
int ans1,ans2;


signed main()
{
     freopen("phigros.in","r",stdin);
     freopen("phigros.out","w",stdout);
    n = read(),m = read(),k = read(),ww = read();

    int cnt = 0;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=k;j++)
        {
            string str;
            str = readStr();
            cnt ++;
            if(str == "Tap")a[cnt] = 1;
            if(str == "Hold")a[cnt] = 2;
            if(str == "Flick")a[cnt] = 3;
            if(str == "Drag")a[cnt] = 4;
//这里将字符串转化为数字，便于后续操作
        }
    }
    for(int i=1;i<=4;i++)
    {
        v[i] = read();
    }
    for(int i=1;i<=4;i++)
    {
        w[i] = read();
    }

    vector<vector<int> > dp(m + 1, vector<int>(ww + 1, 0));
    for(int i=1;i<=m;i++)
    {
        vector<int> cur_w(k);
        vector<int> cur_v(k);
        for(int j=0;j<k;j++)
        {
            cur_w[j] = w[a[(i - 1) * k + j + 1]];
            cur_v[j] = v[a[(i - 1) * k + j + 1]];
/* 对于每一波攻击，先计算当前波中每个道具的实际精力消耗 `cur_w` 和连击数 `cur_v`。*/
        }
        // 枚举当前波使用的手指数量
        for (int use = 0; use <= min((long long)4, k); use++)
        {
/* 枚举使用手指的数量 `use`（最多 4 个），使用位运算生成使用 `use` 个道具的所有组合（通过 `mask`，见代码）。*/
            vector<int> cur_index;
/*对于每一波攻击，枚举使用手指的数量 use（最多为 4 或 k，取较小值）。
然后，使用状态压缩 mask 来表示道具的选择情况，
(1 << k) 表示有 k 个道具时可能的不同组合状态，
总共有2^k种组合。对于每种组合，
__builtin_popcount(mask) 函数计算 mask 中 1 的数量，
当 1 的数量等于 use 时，
表示使用 use 个道具的一种组合，
将该 mask 存储在 cur_index 中。
总结来说，cur_index 存储的是当前波次攻击中，
使用 use 个道具的所有可能组合。
这样，后续代码可以根据存储在 cur_index 中的mask来计算不同道具组合下的精力消耗和连击数，
并更新dp。*/

            for (int mask = 0; mask < (1 << k); mask++)
            {
                if (__builtin_popcount(mask) == use)
                {/*__builtin_popcount()函数计算的是
mask的二进制表示中有多少个1，
在这里就是枚举每一个道具选或不选
的总方案数*/
                    cur_index.push_back(mask);
                }
            }
            for (int mask : cur_index)
            {
                int cur_w_sum = 0;
                int cur_v_sum = 0;
//* 计算每种组合的精力消耗 `cur_w_sum` 和连击数 `cur_v_sum`，并更新 `dp` 数组。
                for (int j = 0; j < k; j++)
                {
                    if ((mask >> j) & 1)
                    {
                        cur_w_sum += cur_w[j];
                        cur_v_sum += cur_v[j];
                    }
                }
                for (int j = 0; j <= ww; j++)
                {
                    if (j >= cur_w_sum)
                    {
                        dp[i][j] = max(dp[i][j], dp[i - 1][j - cur_w_sum] + cur_v_sum);
/** `dp[i][j]` 表示处理完第 `i` 波攻击后，剩余精力为 `j` 时的最大连击数。*/
                    }
                }
            }
        }
    }
    ans1 = 0;
    for(int j=0;j<=ww;j++)
    {
        ans1 = max(ans1, dp[m][j]);
    }
    ans1 %= mod;
    write(ans1);
    putchar(' ');

    int cur_energy = ww;
    int cur_attack = 0;
    for (int i = m; i >= 1; i--)
    {/* 计算最多能抵挡的攻击次数：
  
  * 从最后一波开始向前遍历，
同样枚举使用手指的数量和道具组合，
找到能让当前 `dp` 值等于上一波 `dp` 值
加上当前组合连击数的情况，
更新精力并增加抵挡攻击次数 `cur_attack`。*/
        for (int use = 0; use <= min((long long)4, k); use++)
        {
            vector<int> cur_index;
            for (int mask = 0; mask < (1 << k); mask++)
            {
                if (__builtin_popcount(mask) == use)
                {
                    cur_index.push_back(mask);
                }
            }
            for (int mask : cur_index)
            {
                int cur_w_sum = 0;
                int cur_v_sum = 0;
                for (int j = 0; j < k; j++)
                {
                    if ((mask >> j) & 1)
                    {
                        cur_w_sum += w[a[(i - 1) * k + j + 1]];
                        cur_v_sum += v[a[(i - 1) * k + j + 1]];
                    }
                }
                if (cur_energy >= cur_w_sum && dp[i][cur_energy] == dp[i - 1][cur_energy - cur_w_sum] + cur_v_sum)
                {
                    cur_energy -= cur_w_sum;
                    cur_attack++;
                    break;
                }
            }
        }
    }
    write(cur_attack);
    return 0;
}