题意按照我的理解就是相当于一个具有多个重量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; }
全部评论
(0) 回帖