网站设计项目书_企业网站建设讲解_中国十大网站有哪些_活动推广方式

P11044 [蓝桥杯 2024 省 Java B] 食堂

题目描述

S 学校里一共有 $a_2$ 个两人寝、$a_3$ 个三人寝，$a_4$ 个四人寝，而食堂里有 $b_4$ 个四人桌和 $b_6$ 个六人桌。学校想要安排学生们在食堂用餐，并且满足每个寝室里的同学都在同一桌就坐，请问这个食堂最多同时满足多少同学用餐？

输入格式

本题采用多组数据输入。

输入共 $q+1$ 行。

第一行为一个正整数 $q$ 表示数据组数。

后面 $q$ 行，每行五个非负整数 $a_2,a_3,a_4,b_4,b_6$ 表示一组数据。

输出格式

输出共 $q$ 行，每行一个整数表示对应输入数据的答案。

输入输出样例 #1

输入 #1

2
3 0 1 0 1
0 2 2 1 1

输出 #1

6
10

说明/提示

【样例说明】

对于第一组数据，只有一个六人桌，因此最多安排三个两人寝的同学就餐，答案为 $(2+2+2)=6$。

对于第二组数据，用一个六人桌安排两个三人寝的同学，用一个四人桌安排一个四人寝的同学，答案为 $(3+3)+(4)=10$。

【评测用例规模与约定】

对于 $20\%$ 的评测用例，保证 $a_2+a_3+a_4\le 8$。

对于 $100\%$ 的评测用例，保证 $q\le 100$，$b_4+b_6\le a_2+a_3+a_4\le 100$。

题解：因为要安排人尽可能的多，就有必要先把三人寝弄进六人桌里，尽可能先把六人桌凑了然后二人寝和四人寝就更容易安排进四人桌，那么已知三人寝a3个，六人桌b6个，判断6b6-3a3，不够的话即小于0就先不管，如果四人桌有余再来管他们，然后安排四人桌，4b4-4a4-2a2，注意是先减4a4

尝试写了dp,但是题解区似乎没有给dp，附上正确的模拟做法

for (int i = 0; i <= a2; i++) {for (int j = 0; j <= a3; j++) {for (int k = 0; k <= a4; k++) {int c = dp[i][j][k];// 尝试安排一个两人寝if (i + 1 <= a2) {// 优先使用四人桌if (b4 > 0) {dp[i + 1][j][k] = max(dp[i + 1][j][k], c + 2);}// 再考虑六人桌if (b6 > 0) {dp[i + 1][j][k] = max(dp[i + 1][j][k], c + 2);}}// 尝试安排一个三人寝if (j + 1 <= a3) {if (b6 > 0) {dp[i][j + 1][k] = max(dp[i][j + 1][k], c + 3);}}// 尝试安排一个四人寝if (k + 1 <= a4) {if (b4 > 0) {dp[i][j][k + 1] = max(dp[i][j][k + 1], c + 4);}if (b6 > 0) {dp[i][j][k + 1] = max(dp[i][j][k + 1], c + 4);}}}}}

#include<bits/stdc++.h>
using namespace std;
int t,a2,a3,a4,b4,b6;
int main()
{cin>>t;while(t--){int cnt=0;cin>>a2>>a3>>a4>>b4>>b6;while(b4>0&&a4>0)//4人寝室用4人桌{a4--;b4--;cnt+=4;}while(b6>0&&a2>0&&a4>0)//2人寝室和4人寝室用6人桌{a4--;a2--;b6--;cnt+=6;}while(b4>0&&a2-1>0)//两个2人寝室用4人桌{a2-=2;b4--;cnt+=4;}while(b6>0&&a3-1>0)//两个3人寝室用6人桌{a3-=2;b6--;cnt+=6;}while(b6>0&&a2-2>0)//三个2人寝室用6人桌{a2-=3;b6--;cnt+=6;}while(b4>0&&a3>0)//3人寝室用4人桌{a3--;b4--;cnt+=3;}while(b6>0&&a3>0&&a2>0)//2人寝室和3人寝室用6人桌{a3--;a2--;b6--;cnt+=5;}while(b6>0&&a2-1>0)//两个2人寝室用6人桌{a2-=2;b6--;cnt+=4;}while(b4>0&&a2>0)//2人寝室用4人桌{a2--;b4--;cnt+=2;}while(b6>0&&a4>0)//4人寝室用6人桌{a4--;b6--;cnt+=4;}while(b6>0&&a3>0)//3人寝室用6人桌{a3--;b6--;cnt+=3;}while(b6>0&&a2>0)//2人寝室用6人桌{a2--;b6--;cnt+=2;}cout<<cnt<<endl;}return 0;
}