Jaspercheng @ 2024-04-20 17:00:18
#include <bits/stdc++.h>
#define f1(x , y) for(register int i = x ; i <= y ; i++)
#define f2(x , y) for(register int j = x ; j <= y ; j++)
#define ri register int
#define ll long long
#define il inline
#define cs const
using namespace std;
il int rd(){
int out = 0 , flag = 1; char c = getchar();
while(c < '0' || c >'9'){if(c == '-')flag = -1; c = getchar();}
while(c >= '0' && c <= '9'){out = out * 10 + c - '0'; c = getchar();}
return flag * out;
}
cs int N = 6e1 + 10 , M = 3.2e4 + 10;
int n , m , f[M] , x , y;
struct node{int h , u , p , q;}w[N];
vector <int> p[N];
int main(){
n = rd() , m = rd();
f1(1 , m) w[i].h = i , w[i].u = rd() , w[i].p = rd() , w[i].q = rd();
f1(1 , m){if(w[i].q){p[w[i].q].push_back(i); if(p[w[i].q].size() == 3) p[w[i].q].push_back(-1);} else p[i].push_back(i);}
for(int k = 1 ; k <= m ; k++){
if(p[k].empty()) continue;
for(int i = n ; i >= 0 ; i--)
f2(0 , p[i].size() - 1){
if(j == 0) x = w[i].u * w[i].p , y = w[i].u;
if(j == 1 || j == 2) x = w[p[i][j]].u * w[p[i][j]].p + w[i].u * w[i].p , y = w[p[i][j]].u + w[i].u;
if(j == 3) x = w[p[i][1]].u * w[p[i][1]].p + w[p[i][2]].u * w[p[i][2]].p + w[i].u * w[i].p , y = w[p[i][1]].u + w[p[i][2]].u + w[i].u;
if(i < y) continue;
f[i] = max(f[i] , f[i - y] + x);
}
}cout << f[n];
return 0;
}by lry0404 @ 2024-05-30 13:12:35
#include <iostream>
using namespace std;
int n, m, v[65], p[65], q[65], c1[65], c2[65], gv[65][4], gw[65][4], f[32005];
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
cin >> v[i] >> p[i] >> q[i];
if (q[i])
if (c1[q[i]])
c2[q[i]] = i;
else
c1[q[i]] = i;
}
for (int i = 1; i <= m; i++)
{
if(q[i] == 0)
{
for(int j = 0; j <= 1; j++)
{
for(int k = 0; k <= 1; k++)
{
gv[i][j * 2 + k] = j * v[c1[i]] + k * v[c2[i]] + v[i];
gw[i][j * 2 + k] = j * v[c1[i]] * p[c1[i]] + k * v[c2[i]] * p[c2[i]] + v[i] * p[i];
}
}
}
}
for(int i = 1; i <= m; i++)
{
if(q[i] == 0)
{
for(int j = n; j >= 0; j--)
{
for(int k = 0; k < 4; k++)
{
if(j >= gv[i][k])
{
f[j] = max(f[j], f[j - gv[i][k]] + gw[i][k]);
}
}
}
}
}
cout << f[n] << endl;
return 0;
}