#P4271. 第2题-小红书创作
-
1000ms
Tried: 39
Accepted: 23
Difficulty: 4
所属公司 :
华为
时间 :2025年10月22日-非AI方向(通软&嵌软&测试&算法&数据科学)
-
算法标签>动态规划背包
第2题-小红书创作
解题思路
-
这是一个二维约束的 0/1 背包问题:每个朋友是一件物品,消耗时间
ti与脑细胞hi,价值为点赞数ai;总时间不超过T、总脑细胞不超过H,问最大点赞数。 -
动态规划(二维 0/1 背包) 设
dp[t][h]表示在时间上限为t、脑细胞上限为h时能获得的最大点赞数。 对每个朋友进行一次倒序转移:dp[t][h] = max(dp[t][h], dp[t - ti][h - hi] + ai) (t>=ti 且 h>=hi)倒序是为了保证每个朋友只能被选一次(0/1 背包的关键)。
-
答案为
dp[T][H]。
复杂度分析
- 时间复杂度:
O(n * T * H),其中n ≤ 100,T,H ≤ 100,最多约 100 万次转移,完全可行。 - 空间复杂度:
O(T * H),一个二维数组保存状态(≈ 10^4 级别)。
代码实现
Python
# 题面功能函数:二维0/1背包,返回最大点赞数
def max_likes(n, T, H, items):
# dp[t][h]:时间不超过t、脑细胞不超过h的最大点赞
dp = [[0] * (H + 1) for _ in range(T + 1)]
for ti, hi, ai in items:
# 倒序遍历,确保每个朋友只能选一次
for t in range(T, ti - 1, -1):
for h in range(H, hi - 1, -1):
v = dp[t - ti][h - hi] + ai
if v > dp[t][h]:
dp[t][h] = v
return dp[T][H]
# 主函数:读入与输出(ACM风格)
def main():
import sys
data = sys.stdin.read().strip().split()
it = iter(data)
n = int(next(it))
T = int(next(it))
H = int(next(it))
items = []
for _ in range(n):
ti = int(next(it))
hi = int(next(it))
ai = int(next(it))
items.append((ti, hi, ai))
print(max_likes(n, T, H, items))
if __name__ == "__main__":
main()
Java
import java.util.*;
// ACM 风格:类名为 Main
public class Main {
// 题面功能函数:二维0/1背包
static int maxLikes(int n, int T, int H, int[] ti, int[] hi, int[] ai) {
int[][] dp = new int[T + 1][H + 1];
// 枚举每个朋友(物品)
for (int i = 0; i < n; i++) {
// 倒序遍历时间与脑细胞,保证每个朋友至多使用一次
for (int t = T; t >= ti[i]; t--) {
for (int h = H; h >= hi[i]; h--) {
dp[t][h] = Math.max(dp[t][h], dp[t - ti[i]][h - hi[i]] + ai[i]);
}
}
}
return dp[T][H];
}
// 主函数:输入输出
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
if (!sc.hasNextInt()) { sc.close(); return; }
int n = sc.nextInt();
int T = sc.nextInt();
int H = sc.nextInt();
int[] ti = new int[n];
int[] hi = new int[n];
int[] ai = new int[n];
for (int i = 0; i < n; i++) {
ti[i] = sc.nextInt();
hi[i] = sc.nextInt();
ai[i] = sc.nextInt();
}
System.out.println(maxLikes(n, T, H, ti, hi, ai));
sc.close();
}
}
C++
#include <bits/stdc++.h>
using namespace std;
// 题面功能函数:二维0/1背包
int maxLikes(int n, int T, int H, const vector<int>& t, const vector<int>& h, const vector<int>& a) {
// dp[t][h]:时间不超过t、脑细胞不超过h的最大点赞
vector<vector<int>> dp(T + 1, vector<int>(H + 1, 0));
for (int i = 0; i < n; ++i) {
// 倒序遍历,确保每个朋友只能选择一次
for (int tt = T; tt >= t[i]; --tt) {
for (int hh = H; hh >= h[i]; --hh) {
dp[tt][hh] = max(dp[tt][hh], dp[tt - t[i]][hh - h[i]] + a[i]);
}
}
}
return dp[T][H];
}
// 主函数:读入与输出(ACM风格)
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if (!(cin >> n)) return 0;
int T, H;
cin >> T >> H;
vector<int> t(n), h(n), a(n);
for (int i = 0; i < n; ++i) {
cin >> t[i] >> h[i] >> a[i];
}
cout << maxLikes(n, T, H, t, h, a) << "\n";
return 0;
}
题目内容
小朱同学看到小红书上有很多外国人涌入,于是决定给这些外国人展示他与朋友们的日常生活。
已知他有 n 个朋友,分享他第 i 个朋友的故事需要花费 Ti 的时间和 Hi 的脑细胞来编辑文章,并在发表后能获得 Ai 的点赞量。
请问:在花费总时间不超过 T 且总脑细胞不超过 H 的前提下,最多可以获得多少点赞量?
提示:1<=n<=100
1<=H、T、ti、hi、ai<=100
输入描述
第一行输入一个正整数 n ,代表朋友的数量。
第二行输入两个正整数 T 和 H ,代表时间限制和脑细胞限制(脑细胞不会重生)。空格隔开
接下来的 n 行,每行输入三个正整数 ti,hi,ai,代表分享第 i 个朋友的故事需要花费 ti 的时间、hi 的脑细胞,然后能获得 ai 的点赞量,空格隔开。
输出描述
最多可以获得的点赞量
样例1
输入
2
5 4
1 5 2
6 2 3
输出
0
说明
时间或脑细胞无法完成任何一项创作,故获得 0 点赞量
样例2
输入
3
5 4
1 2 2
2 1 3
4 1 5
输出
7
说明
在不超过限制的情况下,分享第 1 个和第 3 个朋友的故事可获得的点赞量最高,为 7