ABC-390-E - Vitamin Balance

思路讲解

我的总体思路就是把问题拆成3个背包，而且因为不同食物不会含有多种vitamin，所以背包之间不会有干扰。

然后枚举前两个背包的大小（第三个背包就是总背包-1-2），得出最优组合，输出答案即可

AC代码

AC

https://atcoder.jp/contests/abc390/submissions/62196209

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=5010,MAXval=static_cast<ll> (1e18)+3;

ll N,T,C;
struct Food{
	ll unit,ene;
};
vector<Food> food[5];
// 该容量（卡路里）下，该卡路里摄入量最多是多少？
ll dp[5][MAXN];
ll Len[5];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>C;
	FOR(i, 1, N){
		ll kind,unit,ene;
		cin>>kind>>unit>>ene;
		food[kind].push_back((Food){unit,ene});
	}
	Len[1]=food[1].size();Len[2]=food[2].size();Len[3]=food[3].size();
	// 计算三种元素的背包问题答案
	FOR(i, 1, 3){
		FOR(j, 0, Len[i]-1){	// 枚举物品种类
			ROF(k, C, food[i][j].ene){	// 枚举背包容量
				dp[i][k]=max(dp[i][k],dp[i][k-food[i][j].ene]+food[i][j].unit);
			}
		}
	}
	ll ans=0;
	FOR(i, 0, C){
		FOR(j, 0, C-i){
			ans=max(min({dp[1][i],dp[2][j],dp[3][C-i-j]}),ans);
		}
	}
	cout<<ans<<'\n';
	return 0;
}

心路历程（WA，TLE，MLE……）