打卡信奥刷题（2020）用C++实现信奥 P10987 [蓝桥杯 2023 国 Python A] 火车运输

rogeliu

466人浏览 · 2025-09-11 08:20:40

rogeliu · 2025-09-11 08:20:40 发布

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

题目背景

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

题目描述

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

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

输入格式

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

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

输出格式

输出一个整数表示答案。

输入输出样例 #1

输入 #1

3 10 8
8 9 1

输出 #1

说明/提示

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

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

样例解释

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

C++实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
int dp[1001][1001];
int A[3];
int v[201];
signed main()
{
	int n , a , b;
	cin >> n >> A[1] >> A[2];
	for(int i = 1;i <= n;++ i)
	cin >> v[i];
	for(int i = 1;i <= n;++ i)
	for(int j = A[1];j >= 0;-- j)
	for(int k = A[2];k >= 0;-- k)
	{	
		if(j >= v[i])
			dp[j][k] = max(dp[j][k] , dp[j - v[i]][k] + v[i]);
		if(k >= v[i])
			dp[j][k] = max(dp[j][k] , dp[j][k - v[i]] + v[i]);
	}
	
	cout << dp[A[1]][A[2]];
	return 0;
}