多校第三场 A PACM Team(01背包)

题意按照我的理解就是相当于一个具有多个重量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 MAX = 38;
int dp[MAX][MAX][MAX][MAX];
bool path[MAX][MAX][MAX][MAX][MAX];
int p[MAX],a[MAX],c[MAX],m[MAX], g[MAX], cnt[MAX];
int N,P,A,C,M;
void solve(){
    memset(dp,0,sizeof(dp));
    memset(path,0,sizeof(path));
    //01背包的标准样式
    for(int i=0;i<N;++i){
        for(int j=P;j >= p[i];--j){
            for(int k=A;k >= a[i];--k){
                for(int l=C;l >= c[i];--l){
                    for(int o=M;o >= m[i];--o){
                        if(dp[j][k][l][o] < dp[j-p[i]][k-a[i]][l-c[i]][o-m[i]] + g[i]){
                            dp[j][k][l][o] = dp[j-p[i]][k-a[i]][l-c[i]][o-m[i]] + g[i];
                            path[i][j][k][l][o] = true;//如果被更新就标记这个情况为true
                            //这里，最开始我用的序号是dp[o][l][k][j]，比赛时可以过，现在似乎会超时,可能是跟访问地址有关？
                        }
                    }
                }
            }
        }
    }
    //从最后的情况向前找就可以了。
    vector<int> vec;
    for(int i=N-1,j=P,k=A,l=C,o=M;i>=0&&j>=0&&k>=0&&l>=0&&o>=0;--i){
        if(path[i][j][k][l][o]){//表示这个物品被使用了。
            vec.push_back(i);
            j -= p[i];
            k -= a[i];
            l -= c[i];
            o -= m[i];
        }
    }
    cout << vec.size() << endl;
    reverse(vec.begin(),vec.end());
    for(vector<int>::iterator it = vec.begin();it != vec.end();++it){
        cout << *it << endl;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N;
    for(int i=0;i<N;++i){
        cin >> p[i] >> a[i] >> c[i] >> m[i] >> g[i];
    }
    cin >> P >> A >> C >> M;
    solve();
    return 0;
}