2018牛客网暑期ACM多校训练营(第三场) A - PACM Team - [四维01背包][四约束01背包]
题目链接:https://www.nowcoder.com/acm/contest/141/A
空间限制:C/C++ 262144K,其他语言524288K
Special Judge, 64bit IO Format: %lld
题目描述
Since then on, Eddy found that physics is actually the most important thing in the contest. Thus, he wants to form a team to guide the following contestants to conquer the PACM contests(PACM is short for Physics, Algorithm, Coding, Math).
There are N candidate groups each composed of pi physics experts, ai algorithm experts, ci coding experts, mi math experts. For each group, Eddy can either invite all of them or none of them. If i-th team is invited, they will bring gi knowledge points which is calculated by Eddy's magic formula. Eddy believes that the higher the total knowledge points is, the better a team could place in a contest. But, Eddy doesn't want too many experts in the same area in the invited groups. Thus, the number of invited physics experts should not exceed P, and A for algorithm experts, C for coding experts, M for math experts.
Eddy is still busy in studying Physics. You come to help him to figure out which groups should be invited such that they doesn't exceed the constraint and will bring the most knowledge points in total.
输入描述:
输出描述:
The first line should contain a non-negative integer K indicating the number of invited groups.
The second line should contain K space-separated integer indicating the index of invited groups(groups are indexed from 0). You can output index in any order as long as each index appears at most once. If there are multiple way to reach the most total knowledge points, you can output any one of them. If none of the groups will be invited, you could either output one line or output a blank line in the second line.
输入
2
1 0 2 1 10
1 0 2 1 21
1 0 2 1
输出
1
1
输入
1
2 1 1 0 31
1 0 2 1
输出
0
题意&题解:
背包有四个约束P,A,C,M(相当于四种容量),每个物品有对应的四种体积p,a,c,m,同时还有一个价值g,问选哪些物品使得不超容量的情况下价值最大。
即一个四个约束条件的01背包,适当修改一下01背包模板即可。
另外,本题卡空间复杂度,int类型的dp数组只能开四维,所以就要用滚动数组压缩,
另外本题需要知道的是选择了哪些物品,所以开一个五维的bool类型数组存储是否选取该物品即可(365B ≈ 60000 KB,不会超空间限制)。
AC代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=; int n;
int p[maxn],a[maxn],c[maxn],m[maxn],g[maxn];
int P,A,C,M; int dp[maxn][maxn][maxn][maxn];
bool pick[maxn][maxn][maxn][maxn][maxn]; vector<int> ans; int main()
{
cin>>n;
for(int i=;i<n;i++) cin>>p[i]>>a[i]>>c[i]>>m[i]>>g[i];
cin>>P>>A>>C>>M; for(int i=;i<n;i++)
{
for(int pp=P;pp>=;pp--)
{
for(int aa=A;aa>=;aa--)
{
for(int cc=C;cc>=;cc--)
{
for(int mm=M;mm>=;mm--)
{
if(pp<p[i]||aa<a[i]||cc<c[i]||mm<m[i])
{
dp[pp][aa][cc][mm] = dp[pp][aa][cc][mm];
pick[i][pp][aa][cc][mm] = ;
}
else
{
if(dp[pp][aa][cc][mm] < dp[pp-p[i]][aa-a[i]][cc-c[i]][mm-m[i]]+g[i])
{
dp[pp][aa][cc][mm] = dp[pp-p[i]][aa-a[i]][cc-c[i]][mm-m[i]] + g[i];
pick[i][pp][aa][cc][mm] = ;
}
else
{
dp[pp][aa][cc][mm] = dp[pp][aa][cc][mm];
pick[i][pp][aa][cc][mm] = ;
}
}
}
}
}
}
} ans.clear();
for(int i=n-;i>=;i--)
{
if(pick[i][P][A][C][M])
{
ans.push_back(i);
P-=p[i], A-=a[i], C-=c[i], M-=m[i];
}
if(P<||A<||C<||M<) break;
} cout<<ans.size()<<endl;
for(int i=;i<ans.size();i++)
{
if(i!=) printf(" ");
printf("%d",ans[i]);
}
}
注:用滚动数组压缩时要记得要逆序枚举容量,当然本题不逆序也可以过(因为我忘记逆序枚举容量交了一发过了),但是保持严谨性还是逆序枚举比较好。
最新文章
- Python快速建站系列-Part.Five.3-个人主页及资料页面
- Linux之RHEL6的开机流程分析
- 弹出框四 之toastr.js (完成提示框)
- linux chmod 命令
- Excel中设置下拉列表的来源怎么选择其他工作表的内容
- ionic ngcordova map 地圖
- SUSE linux ,liveUSB制作方法
- 详解C/C++函数指针声明
- DataGrid列的合并
- BootStrap Progressbar 实现大文件上传的进度条
- c#调用钩子
- Centos7下安装pip
- mybatis中传入一个List集合作为查询条件的参数
- NanUI文档 - 如何实现C#与Javascript的相互通信
- C#下RSA算法的实现(适用于支付宝和易宝支付)
- linux子系统搭建python3
- bootstrap之navbar
- bitbucket 上公钥SSH key如何add key并进行项目运用
- mybatis DATE_FORMAT 格式化时间输出
- Java包装类及其拆箱装箱