PACM Team(牛客第三场多校赛+dp+卡内存+打印路径)

时间:2022-11-25 21:14:17

题目链接(貌似未报名的不能进去):https://www.nowcoder.com/acm/contest/141/A

题目:

PACM Team(牛客第三场多校赛+dp+卡内存+打印路径)

PACM Team(牛客第三场多校赛+dp+卡内存+打印路径)

题意:背包题意,并打印路径。

思路:正常背包思路,不过五维的dp很容易爆内存,比赛时无限爆,后面队友提醒用short就过了。不过也可以用滚动减少内存消耗,两种代码实现都贴一下吧~

五维代码实现如下:

 1 #include <set>
 2 #include <map>
 3 #include <queue>
 4 #include <stack>
 5 #include <cmath>
 6 #include <bitset>
 7 #include <cstdio>
 8 #include <string>
 9 #include <vector>
10 #include <cstdlib>
11 #include <cstring>
12 #include <iostream>
13 #include <algorithm>
14 using namespace std;
15 
16 typedef long long ll;
17 typedef unsigned long long ull;
18 
19 #define lson i<<1
20 #define rson i<<1|1
21 #define bug printf("*********\n");
22 #define FIN freopen("D://code//in.txt", "r", stdin);
23 #define debug(x) cout<<"["<<x<<"]" <<endl;
24 #define IO ios::sync_with_stdio(false),cin.tie(0);
25 
26 const double eps = 1e-8;
27 const int mod = 10007;
28 const int maxn = 1e7 + 7;
29 const double pi = acos(-1);
30 const int inf = 0x3f3f3f3f;
31 const ll INF = 0x3f3f3f3f3f3f3f3f;
32 
33 short n, P, A, C, M;
34 short p[37], a[37], c[37], m[37], g[37], cnt[37];
35 short dp[37][37][37][37][37];
36 bool vis[37][37][37][37][37];
37 
38 int main() {
39     //FIN;
40     cin >>n;
41     for(int i = 1; i <= n; i++) {
42         cin >>p[i] >>a[i] >> c[i] >>m[i] >>g[i];
43     }
44     cin >>P >>A >>C >>M;
45     int flag1 = 0, flag2 = 0, flag3 = 0, flag4 = 0, mx = 0;
46     for(int i = 1; i <= n; i++) {
47         for(int j = 0; j <= P; j++) {
48             for(int k = 0; k <= A; k++) {
49                 for(int l = 0; l <= C; l++) {
50                     for(int t = 0; t <= M; t++) {
51                         dp[i][j][k][l][t] = dp[i-1][j][k][l][t];
52                         if(j >= p[i] && k >= a[i] && l >= c[i] && t >= m[i]) {
53                             if(dp[i-1][j-p[i]][k-a[i]][l-c[i]][t-m[i]] + g[i] > dp[i-1][j][k][l][t]) {
54                                 dp[i][j][k][l][t] = dp[i-1][j-p[i]][k-a[i]][l-c[i]][t-m[i]] + g[i];
55                                 vis[i][j][k][l][t] = true;
56                             }
57                         }
58                     }
59                 }
60             }
61         }
62     }
63     for(int j = 0; j <= P; j++) {
64         for(int k = 0; k <= A; k++) {
65             for(int l = 0; l <= C; l++) {
66                 for(int t = 0; t <= M; t++) {
67                     if(dp[n][j][k][l][t] > mx) {
68                         flag1 = j, flag2 = k, flag3 = l, flag4 = t;
69                         mx = dp[n][j][k][l][t];
70                         
71                     }
72                 }
73             }
74         }
75     }
76     int num = 0;
77     for(int i = n; i >= 1; i--) {
78         if(vis[i][flag1][flag2][flag3][flag4]) {
79             cnt[num++] = i - 1;
80             flag1 -= p[i];
81             flag2 -= a[i];
82             flag3 -= c[i];
83             flag4 -= m[i];
84         }
85     }
86     cout <<num <<endl;
87     for(int i = num - 1; i >= 0; i--) {
88         cout <<cnt[i] <<" ";
89     }
90     cout <<"\n";
91     return 0;
92 }

 

滚动数组实现如下:

 1 #include <bits/stdc++.h>
 2 #define fi first
 3 #define se second
 4 #define lson l,m,rt<<1
 5 #define rson m+1,r,rt<<1|1
 6 #define lowbit(x) x&-x
 7 #define MP make_pair
 8 #define pb push_back
 9 #define debug(x) cout<<"x= "<<x<<endl;
10 #define FIN freopen("in.txt","r",stdin);
11 using namespace std;
12 typedef long long ll;
13 typedef vector<int> vi;
14 typedef pair<int,int>pii;
15 const int mod=1e9+7;
16 const ll infll=0x3f3f3f3f3f3f3f3f;
17 const int MX = 1e5 + 7;
18 const int INF = 0x3f3f3f3f;
19   
20 short n;
21 short dp[37][37][37][37];
22 bool vis[37][37][37][37][37];
23 short p[37],a[37],c[37],m[37],g[37];
24 short P,A,C,M;
25   
26 int main(){
27     //FIN;
28     cin>>n;
29     for(int i=1;i<=n;i++)
30         cin>>p[i]>>a[i]>>c[i]>>m[i]>>g[i];
31     cin>>P>>A>>C>>M;
32     memset(dp,0,sizeof(dp));
33     memset(vis,0,sizeof(vis));
34     for(int i=1;i<=n;i++){
35         for(int j=P;j>=p[i];j--){
36             for(int k=A;k>=a[i];k--){
37                 for(int l=C;l>=c[i];l--){
38                     for(int o=M;o>=m[i];o--){
39                         if(dp[j][k][l][o] > dp[j-p[i]][k-a[i]][l-c[i]][o-m[i]]+g[i]) continue;
40                         dp[j][k][l][o]=dp[j-p[i]][k-a[i]][l-c[i]][o-m[i]]+g[i];
41                         vis[i][j][k][l][o]=1;
42                     }
43                 }
44             }
45         }
46     }
47     int ans[37],num=0;
48     while(n){
49         if(vis[n][P][A][C][M]){
50             P-=p[n];
51             A-=a[n];
52             C-=c[n];
53             M-=m[n];
54             ans[++num]=n-1;
55         }n--;
56     }
57     printf("%d\n",num);
58     for(int i=num;i>=1;i--)
59         printf("%d ",ans[i]);
60     printf("\n");
61     return 0;
62 }