P10987 [蓝桥杯 2023 国 Python A] 火车运输

P10987 [蓝桥杯 2023 国 Python A] 火车运输

题目背景

为照顾 Python 语言的效率，本题时限较大。建议使用 PyPy3 提交本题。

题目描述

钢厂有一辆用于运送废旧钢材的火车，它具有两节车厢，其中车厢 1 的最大载重量为 $A$，车厢 2 的最大载重量为 $B$。现在一共有 $N$ 件废旧钢材需要被运输，其中第 $i$ 件钢材的重量为 wiw_iwi​，为了最大化运输效率，车长想要一次性运输走重量尽可能多的钢材，请你帮助车长计算出一次运输最多可以带走多大重量的钢材。

每件钢材都是独立的不可分割的，只能被放置在某一节车厢中。在装载钢材时只需要考虑重量条件即可。

输入格式

输入的第一行包含三个整数 $N,A,B$，用一个空格分隔，分别表示钢材的数目以及两节车厢的最大载重。

第二行包含 $N$ 个整数，分别表示 w1,w2,⋯ ,wnw_1,w_2, \\cdots,w_nw1​,w2​,⋯,wn​，相邻两个整数之间使用一个空格分隔。

输出格式

输出一个整数表示答案。

输入输出样例 #1

输入 #1

3 10 88 9 1

输出 #1

18

说明/提示

对于 $30\%$ 的评测用例，$1\le N\le 10$；

对于所有评测用例，1≤N≤200,1≤wi,A,B≤10001 \\le N \\le 200,1 \\le w_i,A,B \\le 10001≤N≤200,1≤wi​,A,B≤1000。

样例解释

车厢 1 装入第 $2$ 件和第 $3$ 件钢材，车厢 2 装入第 $1$ 件钢材。

#includeusing namespace std;const int N=110;#define int long longint dp[1010][1010]; // 定义dp数组signed main(){ int n, a, b; int aa[N]; cin >> n >> a >> b; for(int i = 1; i <= n; i++) cin >> aa[i]; for(int i = 1; i <= n; i++) { for(int j = 0; j <= a; j++) { for(int k = 0; k <= b; k++) { if(j >= aa[i]) {  dp[j][k] = max(dp[j][k], dp[j - aa[i]][k] + aa[i]); } if(k >= aa[i]) {  dp[j][k] = max(dp[j][k], dp[j][k - aa[i]] + aa[i]); } } } } cout << dp[a][b] << endl; return 0;}