Divinsword_Liao @ 2023-12-03 14:56:51
#include <bits/stdc++.h>
using namespace std;
int l[65], v[65][4], p[65][4], dp[32005];
inline int read ()
{
int w = 0; char ch = 0;
while (ch < '0' || ch > '9')
ch = getchar();
while (ch >= '0' && ch <= '9')
w = w * 10 + ch - '0', ch = getchar();
return w;
}
int main()
{
int n = read(), m = read(), len = 1;
for (int i = 1; i <= m; i ++)
{
int vi = read(), pi = read(), q = read();
if (q)
{
v[q][++l[q]] = vi + v[q][l[q] - 1];
p[q][l[q]] = pi * vi + p[q][l[q] - 1];
if (l[q] == 2)
{
v[q][++l[q]] = vi + v[q][0];
p[q][l[q]] = pi * vi + p[q][0];
}
}
else v[len][0] = vi, p[len][0] = pi * vi, len ++;
}
for (int i = 1; i < len; i ++)
for (int j = n; j >= v[i][0]; j --)
for (int k = 0; k <= l[i]; k ++)
if (j >= v[i][k])
dp[j] = max (dp[j], dp[j - v[i][k]] + p[i][k]);
else break;
printf ("%d\n", dp[n]);
return 0;
}到底是哪错了？ 还是编译器炸了？
by csluogu @ 2023-12-03 15:46:31
我没用dp，AC了，感觉你代码复杂了点
#include <bits/stdc++.h>
using namespace std;
const int N = 32005;
int n, m, mw[N], mv[N], fw[N][3], fv[N][3], f[N], v, p, q;
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i ++) {
cin >> v >> p >> q;
if (!q) {
mw[i] = v;
mv[i] = v * p;
}
else {
fw[q][0] ++;
fw[q][fw[q][0]] = v;
fv[q][fw[q][0]] = v * p;
}
}
for (int i = 1; i <= m; i ++) {
for (int j = n; j >= mw[i]; j --) {
f[j] = max(f[j], f[j - mw[i]] + mv[i]);
if (j >= mw[i] + fw[i][1]) f[j] = max(f[j], f[j - mw[i] - fw[i][1]] + mv[i] + fv[i][1]);
if (j >= mw[i] + fw[i][2]) f[j] = max(f[j], f[j - mw[i] - fw[i][2]] + mv[i] + fv[i][2]);
if (j >= mw[i] + fw[i][1] + fw[i][2])
f[j] = max(f[j], f[j - mw[i] - fw[i][1] - fw[i][2]] + mv[i] + fv[i][1] + fv[i][2]);
}
}
cout << f[n] <<endl;
return 0;
}