作为T1，当然是越水越好啦qwq

显然经目测可得，那个所谓的质量评级根本就没卵用，可以直接\(W_i = W_i^{V_i}\)累积到利润里面。

这样，本问题显然是一个“子集和”问题的模板。此类问题一般使用暴力DFS或DP解决。对于本题，由于体积过大，使用DFS。（听说DP也可以解？算了出题人太懒不写了qwq）

不难发现，此题爆搜的时间复杂度为\(O(2^n)\)，可以拿20分。

对于更大的数据，考虑以双向DFS的形式，降低复杂度。

DFS框架：把矿脉分为两部分，先预处理出数组\(save\)，存储前一半矿脉中可能组合出的利润值，并对其进行升序排序。随后对于后一半矿脉中每一个可能达到的利润值\(k\)，在\(save\)中二分查找一个数值\(res\)，在\(res+k≤S\)的同时使\(res\)最大，用\(res+k\)更新答案。

搜索面对的状态：正在搜索第\(i\)个矿脉、当前利润值\(x\)、正在执行\(pos\)这一半矿脉的搜索。

剪枝：

1.优化搜索顺序

开始搜索之前，将矿脉降序排序。

2.可行性剪枝

在第二次搜索中，如果当前利润加上\(save\)数组中的最小利润大于\(S\)，剪枝。

运用以上技巧，可将时间复杂度降低到\(O(2^{\frac{n}{2}}log_22^{\frac{n}{2}})\)，可以AC此题。

然而此正解被某歪解疯狂卡卡成了歪解qwq

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

long long w[53], s, n, ans, save[1 << 25], t = 0;

bool cmp(long long x, long long y) {

	return x > y;

}

void find(long long x) {

    long long f = s - x, a = 0, b = t-1, mid;

    while (b - a > 1) {

        mid = (a+b)/2;

        if(save[mid] < f) {

           	a = mid;

            continue;

        }

        if  (save[mid]==f) {//正好满足

            ans = s;

            return;

        }

        b = mid-1;

    }

    if (save[a]+x <= s && save[a]+x > ans) ans = save[a]+x;

    if (save[b]+x <= s && save[b]+x > ans) ans = save[b]+x;//特判更新答案

}

void dfs(long long i, long long x, bool pos) {//pos为0表示第一次搜索，为1表示第二次搜索

    if (ans == s) return;

    if (x > s) return;

    if (!pos)

      if (i == n/2+1) {

        save[t++] = x;//保存结果

        return;

      }

    if (pos)

      if (i == n+1) {

        find(x);//二分查找

        return;

      }

    dfs(i+1, x, pos);//不选

    dfs(i+1, x+w[i], pos);//选

}     

int main()

{

    scanf("%d%d", &s, &n);

    ans = 0;

    int x;

    for (register int i = 1; i <= n; i++) {

    	scanf("%d%d", &w[i], &x);

    	w[i] = pow(w[i], x);

    }

    sort(w+1, w+n+1, cmp);//优化搜索顺序

    dfs(1, 0, 0);

    sort(save, save+t);

    dfs(n/2+1, 0, 1);

    printf("%d\n",ans);

}