题解 | #购物单#
购物单
https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
#include <array> #include <iostream> using namespace std; const int N = 65; array<array<int, 33000>, N> f; array<array<int, 5>, N> a={0}; //a[i][0]表示编号为i的主件拥有的附件的数量,其余为附件编号 array<int, 65>pri={0}, impo={0}, qq={0}; int n, m; int main() { cin >> n >> m; int v, p, q; for (int i = 1; i <= m; i++) { //初始化 cin >> v >> p >> q; pri[i] = v; impo[i] = p; qq[i] = q; if (q != 0) { a[q][0]++; a[q][a[q][0]] = i; } } for (int i = 1; i <= m; i++) { if (qq[i] == 0) { for (int j = 0; j <= n; j++) { f[i][j] = f[i - 1][j]; if (j >= pri[i]) f[i][j] = max(f[i][j], f[i - 1][j - pri[i]] + pri[i] * impo[i]); if (a[i][0] == 1 && j >= (pri[i] + pri[a[i][1]])) f[i][j] = max(f[i][j], f[i - 1][j - pri[i] - pri[a[i][1]]] + pri[i] * impo[i] + pri[a[i][1]] * impo[a[i][1]]); if (a[i][0] == 2) { if (j >= (pri[i] + pri[a[i][1]])) f[i][j] = max(f[i][j], f[i - 1][j - pri[i] - pri[a[i][1]]] + pri[i] * impo[i] + pri[a[i][1]] * impo[a[i][1]]); if (j >= (pri[i] + pri[a[i][2]])) f[i][j] = max(f[i][j], f[i - 1][j - pri[i] - pri[a[i][2]]] + pri[i] * impo[i] + pri[a[i][2]] * impo[a[i][2]]); if (j >= (pri[i] + pri[a[i][1]]+ pri[a[i][2]])) f[i][j] = max(f[i][j], f[i - 1][j - pri[i] - pri[a[i][1]]- pri[a[i][2]]] + pri[i] * impo[i] + pri[a[i][1]] * impo[a[i][1]]+pri[a[i][2]] * impo[a[i][2]]); } } } else for(int j=0;j<=n;j++) f[i][j]=f[i-1][j]; } cout<<f[m][n]<<endl; return 0; } // 64 位输出请用 printf("%lld")