作为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);
}