日常训练2025-1-8

E小红的双生英雄

https://ac.nowcoder.com/acm/contest/99784/E

思路

读题后跟容易发现是一道分组背包的题，转移也比较简单。有一个做动态规划题的技巧是，如果题目相较于传统的DP题有一些其他的约束条件，则把约束条件写成DP的一个维度就行。

代码

#include <bits/stdc++.h>

typedef std::pair<long long, long long> pll;
typedef std::pair<int, int> pii;
#define INF 0x3f3f3f3f
#define MOD 998244353
using i64 = long long;
const int N = 1e5+5;

void solve(){
	int n, C, m;
	std::cin >> n >> C >> m;

	std::vector<pll> tmp(n+1);
	std::vector<bool> st(n+1);

	for (int i = 1; i <= n; i++)	{
		int cost, v;
		std::cin >> cost >> v;
		tmp[i] = pll(cost, v);
	}

	std::vector<std::vector<pll>> a;

	for (int i = 0; i < m; i++){
		int u, v, w;
		std::cin >> u >> v >> w;

		st[u] = st[v] = true;

		a.push_back({tmp[u], tmp[v], {tmp[u].first + tmp[v].first, tmp[u].second + tmp[v].second + w}});
	}
	for (int i = 1; i <= n; i++){
		if (!st[i]) a.push_back({tmp[i]});
	}

	std::vector<std::vector<i64>> dp(C+1, std::vector<i64>(5));
	std::vector<std::vector<i64>> ndp(C+1, std::vector<i64>(5));

	for (auto s : a){
		ndp = dp;
		for (int i = 0; i < s.size(); i++){
			auto [cost, atk] = s[i];
			int ok = i == 2;
			for (int j = C; j >= cost; j--){
				for (int k = 4; k >= 1 + ok; k--){
					dp[j][k] = std::max(dp[j][k], ndp[j-cost][k-1-ok] + atk);
				}
			}
		}
	}

	i64 ans = 0;
	for (int j = 0; j <= C; j++){
		for (int k = 0; k <= 4; k++){
			ans = std::max(ans, dp[j][k]);
		}
	}

	std::cout << ans << '\n';

}

signed main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout<<std::setiosflags(std::ios::fixed)<<std::setprecision(2);
	int t = 1, i;
	for (i = 0; i < t; i++){
		solve();
	}
	return 0;
}