← Real problems

noi02p3

hardtree-dpknapsackStatement on DMOJ

CP Lang

22 lines0.3 spec
// noi02p3 Nine-Headed Dragon: the big head eats exactly k fruits including the root, every other
// head at least one; a branch costs when one head eats both ends. With three or more heads the
// small heads alternate freely, so only "big or small" matters per fruit: a tree knapsack over
// how many fruits the big head eats, merged child by child as a min-plus convolution.
let (n, heads, k) = read<(1..=300, 2..=300, 1..=300)>()
domain F = 1..=n
let branches = read<[n - 1](a: F, b: F, cost: 0..=100_000)>()
let t = Rooted(Graph.undirected(branches), root: F.first!)
let tropical = Semiring(min, +)
enum Head: Small, Big
fn clash(w: Head, wc: Head, c: F) -> Int:
    if w == wc and (w == Head.Big or heads == 2): t.up_arc(c)!.cost else: 0
// eat(v)[w][x]: the cheapest for v's subtree when head w eats v and the big head eats x of its
// fruits.
fn eat(v: F) -> [Head]List<?Int>:
    var best: [Head]List<?Int> = [Head] w => if w == Head.Big: [None, Some(0)] else: [Some(0), None]
    for c in t.children(v):
        let sub = eat(c)
        let via = (w, wc) => convolve(best[w], sub[wc].map(x => x + clash(w, wc, c)).collect(), over: tropical, shape: Curved.Neither)
        best = [Head] w => zip(via(w, Head.Small), via(w, Head.Big)).map(((p, q)) => min(p, q)).collect()
    best
print(if heads - 1 + k > n: -1 else: eat(t.root)[Head.Big][k]!)

Accepted C++

113 lines · 0.20 s on the judge
#include "bits/extc++.h"

using namespace std;

template<class T>
using mpq = priority_queue<T, vector<T>, greater<>>;

template<class T, class U = less<T>>
using rt = __gnu_pbds::tree<T, __gnu_pbds::null_type, U, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;

template<class T>
void dbgh(const T &t) {
	cerr << t << endl;
}

template<class T, class ...U>
void dbgh(const T &t, const U &...u) {
	cerr << t << " | ";
	dbgh(u...);
}

#ifdef DEBUG
#define dbg(...) cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" << ": "; dbgh(__VA_ARGS__)
#else
#define cerr if(false) cerr
#define dbg(...) 1412
#endif

//imagine a language where int = long
#define long int64_t

//typing too hard
#define endl "\n"

#define sz(x) static_cast<int>((x).size())

#define inline inline __attribute__((always_inline))

const int maxn = 300;

bool add;
int siz[maxn], memo[maxn][maxn][2];
vector<pair<int, int>> graph[maxn];

void pdfs(int u) {
	siz[u] = 1;
	for(auto &[v, w]: graph[u]) {
		graph[v].erase(find(begin(graph[v]), end(graph[v]), pair<int, int> {u, w}));
		pdfs(v);
		siz[u] += siz[v];
	}
}

int dp(int u, int k, int cur) {
	int &ans = memo[u][k][cur];
	k -= cur;
	if(ans != -1) {
		return ans;
	}else if(k < 0 || k > siz[u] - 1) {
		return ans = 1e9;
	}
	int cdp[k + 1];
	fill(cdp, cdp + k + 1, 1e9);
	cdp[0] = 0;
	for(auto &[v, w]: graph[u]) {
		for(int i = k; i >= 0; i--) {
			int copt = 1e9;
			for(int j = 0; j <= siz[v] && i - j >= 0; j++) {
				copt = min({copt, (add && cur == 0) * w + cdp[i - j] + dp(v, j, 0),
							  (cur == 1) * w + cdp[i - j] + dp(v, j, 1)});
			}
			cdp[i] = copt;
		}
	}
	ans = cdp[k];
	return ans;
}

void solve() {
	int n, m, k;
	cin >> n >> m >> k;
	if(m - 1 + k > n) {
		cout << -1 << endl;
		return;
	}
	for(int i = 0; i < n - 1; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		u--;
		v--;
		graph[u].emplace_back(v, w);
		graph[v].emplace_back(u, w);
	}
	pdfs(0);
	add = m == 2;
	memset(memo, -1, sizeof(memo));
	cout << dp(0, k, 1) << endl;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(ios::failbit);
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
#endif
	int t = 1;
//	cin >> t;
	for(int _ = 1; _ <= t; _++) {
		dbg(_);
//		cout << "Case #" << _ << ": ";
		solve();
	}
}