貌似DP的小问题玄关

学术版

JimmyDong @ 2024-08-10 12:52:44

已知有 k 个集合,分别为 s_1,s_2,...,s_k。

s_1= \{a[1][1],a[1][2],....,a[1][size(s_1)]\}

s_2= \{a[2][1],a[2][2],....,a[2][size(s_2)]\}

......

s_k= \{a[k][1],a[k][2],....,a[k][size(s_k)]\}

从每个集合最多选一个数，问在总和不超过 n 的情况下最大是多少。

size(s_i)\leq 5000,k\leq 5000

貌似是 DP

by bcbgszyzh @ 2024-08-10 13:15:22

这是没时间限制的做法

我叫了 @yx666 继续解决您的问题（因为我（ @bcbgszyzh ）要上课）。

@JimmyDong

by JimmyDong @ 2024-08-10 13:18:35

@bcbgszyzh 好滴

by XuYueming @ 2024-08-10 13:23:11

@JimmyDong 你 n 多大

by XuYueming @ 2024-08-10 13:23:53

@XuYueming 可用 bitset

by JimmyDong @ 2024-08-10 13:24:47

@XuYueming n \leq 5000

上一页 |