题目链接
思路：dp[i][j][k]表示第i个物品，组成两个值为j和k的状态，这样会爆掉，所以状态需要转化一下
首先利用滚动数组，可以省去i这维，然后由于j最大记录到50，所以可以把状态表示成一个二进制数s，转化成dp[k] = s，表示组成k状态能组成s，这样空间复杂度就可以接受了，然后这题时限还可以，就这样去转移，然后记录下路径即可
代码：
#include #include #include using namespace std; const int N = 200005; typedef unsigned long long ull; typedef long long ll; int t, n, q, W[N], T[N], ans[55][N]; ull dp[N]; map LOG; int main() { scanf("%d", &t); for (int i = 0; i < 52; i++) LOG[(1ULL< = T[i]; j--) { ull tmp = dp[j]; if (dp[j - T[i]] == 0) continue; dp[j] |= ((dp[j - T[i]])< 0; k &= (k - 1)) { ll x = k; ans[LOG[(x&(-x))]][j] = i; } } } int m, s; for (int i = 0; i < q; i++) { scanf("%d%d", &m, &s); if (!ans[m][s]) printf("No solution!\n"); else { int v = ans[m][s]; int bo = 0; while (v) { if (bo) printf(" "); else bo = 1; printf("%d", v); m -= W[v]; s -= T[v]; v = ans[m][s]; } printf("\n"); } } } return 0; }