首页 > 代码库 > ZOJ 3769 Diablo III（分组背包）
ZOJ 3769 Diablo III（分组背包）
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3769
题意：
有13种装备，每种装备值可以穿戴一种，特殊的就是双手武器和单手武器，双手武器和单手武器+盾只能选择一种，戒指可以双手各戴一个。每个装备都有一个攻击值和防御值，现在要在防御值至少到达m的情况下可以达到的最大攻击力。
思路：
分组背包题目。
把单手武器和盾组合起来放到双手武器当中，戒指也需要两两组合。
接下来就是一个分组背包了，比较重要的是这道题目需要开二维数组，因为题目要求的是至少要达到m的容量，如果超过了m容量，就需要按m来算。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath>10 #include<map>11 #include<set>12 using namespace std;13 typedef long long ll;14 typedef pair<int,int> pll;15 const int INF = 0x3f3f3f3f;16 const int maxn = 400 + 5;17 18 int n,m;19 int d[15][50005];20 vector<pll> v[15];21 map<string,int> ID;22 23 void init()24 {25 ID["Head"] = 1; ID["Shoulder"] = 2; ID["Neck"] = 3;26 ID["Torso"] = 4; ID["Hand"] = 5; ID["Wrist"] = 6;27 ID["Waist"] = 7; ID["Legs"] = 8; ID["Feet"] = 9;28 ID["Finger"] = 10; ID["Shield"] = 11; ID["Weapon"] = 12;29 ID["Two-Handed"] = 13;30 }31 32 bool cmp(const vector<pll> a, const vector<pll> b)33 {34 return a.size()>b.size();35 }36 37 int main()38 {39 //freopen("in.txt","r",stdin);40 init();41 int T;42 scanf("%d",&T);43 while(T--)44 {45 for(int i=1;i<13;i++) v[i].clear();46 47 scanf("%d%d",&n,&m);48 for(int i=0;i<n;i++)49 {50 int D,T; string s;51 cin>>s>>D>>T;52 v[ID[s]].push_back(make_pair(D,T));53 if(ID[s]==11 || ID[s]==12) v[13].push_back(make_pair(D,T));54 }55 56 //合并单手武器和盾牌57 for(int i=0;i<v[11].size();i++)58 {59 for(int j=0;j<v[12].size();j++)60 {61 v[13].push_back(make_pair(v[11][i].first+v[12][j].first,v[11][i].second+v[12][j].second));62 }63 }64 65 v[11].clear();66 v[12].clear();67 68 //合并戒指并且储存在v[10]中69 int len=v[10].size();70 for(int i=0;i<len;i++)71 {72 for(int j=i+1;j<len;j++)73 {74 v[10].push_back(make_pair(v[10][i].first+v[10][j].first,v[10][i].second+v[10][j].second));75 }76 }77 78 memset(d,-1,sizeof(d));79 sort(v+1,v+14,cmp);80 81 d[0][0]=0;82 for(int i=1;i<=11;i++)83 {84 for(int j=0;j<=m;j++)85 {86 d[i][j]=max(d[i][j],d[i-1][j]); //第i组的状态有第i-1组状态而来87 if(d[i-1][j]==-1) continue;88 for(int k=0;k<v[i].size();k++)89 {90 int tmp=min(v[i][k].second+j,m); //如果容量超过了m，那么就按m来算91 d[i][tmp]=max(d[i][tmp],d[i-1][j]+v[i][k].first); //由第i-1组更新92 }93 }94 }95 printf("%d\n",d[11][m]);96 }97 return 0;98 }
ZOJ 3769 Diablo III（分组背包）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。