鏈接：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 p_i physics experts, a_i algorithm experts, c_i coding experts, m_i 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 g_i 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. 示例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


題意按照我的理解就是相當于一個具有多個重量W的01背包。就是從一個W擴展到P,A,C,M四個屬性。
大概做法就是按照01背包的樣式進行改寫就可以了，因為范圍很小只有36,所以時間復雜度就是個五層的循環，大概O(pow(36,5)) = 6000w左右，不會超時，這里要降一層數組，
就是4層的一個dp數組就夠了。也不會超內存.使用記錄路徑的方法，直到最后再還原回去把加入的物品記錄下來最后再輸出。也就是一個很裸的做法。


#include <bits/stdc++.h>using namespace std;const int m=40;struct node{int P,A,C,M,G; }a[m];int A,B,C,D; int N; int dp[m][m][m][m]; bool path[m][m][m][m][m]={0};//用int超內存了int main() {scanf("%d",&N);for(int i=0;i<N;i++){scanf("%d%d%d%d%d",&a[i].P,&a[i].A,&a[i].C,&a[i].M,&a[i].G);}scanf("%d%d%d%d",&A,&B,&C,&D);for(int i=0;i<N;i++){for(int j=A;j>=a[i].P;j--){for(int k=B;k>=a[i].A;k--){for(int l=C;l>=a[i].C;l--){for(int o=D;o>=a[i].M;o--){if(dp[j][k][l][o]<dp[j-a[i].P][k-a[i].A][l-a[i].C][o-a[i].M]+a[i].G){dp[j][k][l][o]=dp[j-a[i].P][k-a[i].A][l-a[i].C][o-a[i].M]+a[i].G;path[i][j][k][l][o] = 1;}}}}}}vector<int> ans;for(int i=N-1; i>=0 && A>=0 && B>=0 && C >=0 && D>=0 ;i--) {if(path[i][A][B][C][D]) {ans.push_back(i);A -= a[i].P,B -= a[i].A;C -= a[i].C,D -= a[i].M;}}int sz = ans.size();printf("%d\n",sz);for(int i=0;i<sz;i++) {printf(i==sz-1?"%d\n":"%d ",ans[i]);}return 0; }

?

轉載于:https://www.cnblogs.com/Fy1999/p/9384061.html

總結

以上是生活随笔為你收集整理的牛客网暑期ACM多校训练营（第三场）A.PACM Team(多重01背包)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。