本文主要是介绍@牛客网暑期ACM多校训练营（第三场） A; PACM Team (01背包DP)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：https://www.nowcoder.com/acm/contest/141/A
来源：牛客网
Eddy was a contestant participating in ACM ICPC contests. ACM is short for Algorithm, Coding, Math. Since in the ACM contest, the most important knowledge is about algorithm, followed by coding(implementation ability), then math. However, in the ACM ICPC World Finals 2018, Eddy failed to solve a physics equation, which pushed him away from a potential medal.
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 contains a positive integer N indicating the number of candidate groups. Each of following N lines contains five space-separated integer pi, ai, ci, mi, gi indicating that i-th team consists of pi physics experts, ai algorithm experts, ci coding experts, mi math experts, and will bring gi knowledge points. The last line contains four space-separated integer P, A, C, M indicating the maximum possible number of physics experts, algorithm experts, coding experts, and math experts, respectively.1 ≤ N ≤ 360 ≤ pi,ai,ci,mi,gi ≤ 360 ≤ P, A, C, M ≤ 36
输出描述:
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.
示例1
输入
复制
2 1 0 2 1 10 1 0 2 1 21 1 0 2 1
输出
复制
1 1
示例2
输入
复制
1 2 1 1 0 31 1 0 2 1
输出
复制
0
[题意]
n 组 , 每组 有p,a,c,m,g , 现在给P,A,C,M 不超过P,A,C,M的情况下 最大的 价值G 并且记录路径
我们把 p,a,c,m 看成一组, 就是个 01 背包 ,然后需要记录路径.
[代码]
#include <bits/stdc++.h>
#include <stdlib.h>
#include <utility>
#include<ext/rope>
#define findx(x,b,n) lower_bound(b+1,b+1+n,x)-b
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w",stdout)
#define SHUT ios_base::sync_with_stdio(false); cout.setf(ios::fixed); cout.precision(20); cout.tie(nullptr); cin.tie(nullptr);
#define lson rt << 1, l, mid
#define rson rt << 1|1, mid + 1, r#pragma comment(linker, "/STACK:1024000000,1024000000") // 扩栈
//next_permutation(a+1,a+x) 全排列
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())using namespace std;
using namespace __gnu_cxx;typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;const double PI=acos(-1.0);
const int INF=0x3f3f3f3f;
const double esp=1e-6;
const int maxn=1e6+5;
const int MOD=1e9+7;
const int mod=1e9+7;/*********************************head************************/int n,P,A,C,M;
struct node
{int p,a,c,m,g;
}pp[50];int dp[40][40][40][40];
bool state[40][40][40][40][40];
int dis[100];
int main()
{memset(dp,0,sizeof(dp));scanf("%d",&n);rep(i,1,n+1)scanf("%d %d %d %d %d",&pp[i].p,&pp[i].a,&pp[i].c,&pp[i].m,&pp[i].g);scanf("%d %d %d %d",&P,&A,&C,&M);rep(i,1,n+1)per(a,0,P+1)per(b,0,A+1)per(c,0,C+1)per(d,0,M+1){if ( (a >= pp[i].p && b >= pp[i].a && c >= pp[i].c && d >= pp[i].m )&&((dp[a-pp[i].p][b -pp[i].a][c-pp[i].c][d-pp[i].m]+pp[i].g ) > dp[a][b][c][d] ) ) {state[i][a][b][c][d] = true;dp[a][b][c][d] = dp[a-pp[i].p][b -pp[i].a][c-pp[i].c][d-pp[i].m]+pp[i].g ;} elsestate[i][a][b][c][d] = false;}int s = 0;if(dp[P][A][C][M]){int step = n;int PP= P,AA = A, CC = C, MM = M;for(;step>=1;step--){if(state[step][PP][AA][CC][MM]){dis[s++] = step-1;PP-=pp[step].p,AA-=pp[step].a,CC-=pp[step].c,MM-=pp[step].m;}}}else{puts("0\n");return 0;}printf("%d\n",s);sort(dis,dis+s);rep(i,0,s){printf("%d%c",dis[i],i==s-1?'\n':' ');}return 0 ;
}
这篇关于@牛客网暑期ACM多校训练营（第三场） A; PACM Team (01背包DP)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
