题目链接：https://vjudge.net/problem/ZOJ-3769
题意：现在你要去打怪，你有13种装备，每件装备会有伤害和防御两种属性，一般来说，每种装备只可以装备一件，但是特别的，戒指（Finger）你可以同时装备两个，左右手各一个，然后对于“Two-Handed”类的装备，如果你装备这种装备，那么你就不可以装备"Shield", "Weapon"这两种，反之，如果你装备了"Shield", "Weapon"中的任意一种，那么你就不可以装备“Two-Handed”类的装备，现在需要我们求出在达到m点以上防御值的情况下可以达到的最大攻击值。如果无法达到m点防御值，则输出-1。
思路：这题可以转化为分组背包，但是又两个问题要解决，一个是Finger类装备，我们可以把Finger类的装备两两组合，加入Finger类里面，这样就把两个Finger类的装备转化为了一个，然后对于"Shield", "Weapon"这两类，我们也是可以两两组合加入“Two-Handed”类里面去的，当然，为了避免其中一种装备的数量为0，所以可以先将"Shield", "Weapon"这两类分别加入“Two-Handed”，然后在加入两两组合的。我一开始是用结构体数组储存的，一直超时，看了大佬博客，说要先处理数量多的那一类，这样可以节省时间，觉得有道理，但是用结构体数组改了还是一直超时（果然，大佬的代码和我的就是不一样），最后重写代码，改成和他们一样用vector储存就过了，不知道为啥。如果有谁知道的，可以提醒一下我，感谢感谢。
这里开二维数组，其中把防御看做背包容量，但是我们不知道背包容量的上限，题目只说了要大于等于m点防御值，所以我们把m以上的都看成m（为啥别人脑洞就这么大），由于在第k组拿装备的时候需要知道第k-1组的值,所以状态转移方程就是dp[k][i+w[j]]=max(dp[k][i+w[j]]，dp[k-1][i]+v[j])。
代码：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<vector>
#include<set>
#include<cstdio>
#include<string>
#include<deque>
using namespace std;
typedef long long LL;
#define eps 1e-8
#define INF 0x3f3f3f3f
#define maxn 50005
/*struct point{
int u,w;
};
bool operator <(const point &s1,const point &s2)
{
if(s1.v!=s2.v)
return s1.v>s2.v;
else
return s1.u>s2.u;
}*/
struct node{
int v,w;
};
int n,m,k,t;
map<string,int>mp;
vector<node>ve[];
string ss[]={" ","Two-Handed","Finger", "Head", "Shoulder", "Neck", "Torso",
"Hand", "Wrist", "Waist", "Legs","Feet", "Shield", "Weapon"};
int dp[][maxn];
void init()
{
for(int i=;i<=;i++){//给装备编号
mp[ss[i]]=i;
}
}
int main()
{
init();
cin>>t;
while(t--)
{
cin>>n>>m;
for(int i=;i<=;i++){
ve[i].clear();
}
string s;
int w,v;
for(int i=;i<=n;i++){
cin>>s>>v>>w;
int id=mp[s];
ve[id].push_back((node){v,w});
}
memset(dp,-,sizeof(dp));//初始化所有状态都不可达
dp[][]=;//初始化 for(int i=;i<ve[].size();i++){//"Shield", "Weapon"合并到“Two-Handed”
ve[].push_back(ve[][i]);
}
int num1=ve[].size();
int num2=ve[].size();
for(int i=;i<num2;i++){
ve[].push_back(ve[][i]);
for(int j=;j<num1;j++){
ve[].push_back((node){ve[][i].v+ve[][j].v,ve[][i].w+ve[][j].w});
}
} num1=ve[].size();
for(int i=;i<num1;i++){//"Finger"合并
for(int j=i+;j<num1;j++){
ve[].push_back((node){ve[][i].v+ve[][j].v,ve[][i].w+ve[][j].w});
}
} for(int k=;k<=;k++){//枚举组
for(int i=;i<=m;i++){//枚举防御值
dp[k][i]=max(dp[k][i],dp[k-][i]);//现在状态的初值从前一状态来
if(dp[k-][i]==-)//如果前一状态不可达
continue;
for(int j=;j<ve[k].size();j++){//如果前一状态可以到达，那么可以在前一状态的基础上在当前组
//拿一件装备
int min1=min(m,i+ve[k][j].w);
dp[k][min1]=max(dp[k][min1],dp[k-][i]+ve[k][j].v);
}
}
}
cout<<dp[][m]<<endl;
}
return ;
}
结构体数组一直超时的代码：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<vector>
#include<set>
#include<cstdio>
#include<string>
#include<deque>
using namespace std;
typedef long long LL;
#define eps 1e-8
#define INF 0x3f3f3f3f
#define maxn 50005
/*struct point{
int u,w;
};
bool operator <(const point &s1,const point &s2)
{
if(s1.w!=s2.w)
return s1.w>s2.w;
else
return s1.u>s2.u;
}*/
map<string,int>mp;
int dp[][maxn];
int n,m,k,t;
struct node{
int num;
int w[];
int v[];
}zu[];
string s[]={" ", "Two-Handed"," ","Head", "Shoulder", "Neck", "Torso", "Hand", "Wrist", "Waist",
"Legs", "Feet", "Finger", "Shield", "Weapon"};
void init()
{
for(int i=;i<=;i++)
{
mp[s[i]]=i;
}
}
void combine_finger()
{
int c=zu[].num;
if(c==)
return;
if(c==)
{
zu[].num++;
zu[].w[]=zu[].w[];
zu[].v[]=zu[].v[];
return;
}
for(int i=;i<c;i++){
for(int j=i+;j<=c;j++){
zu[].num++;
int k=zu[].num;
zu[].w[k]=zu[].w[i]+zu[].w[j];
zu[].v[k]=zu[].v[i]+zu[].v[j];
}
}
return;
}
void combine_two()
{
int a=zu[].num;
int b=zu[].num;
for(int i=min(a,);i<=a;i++){
for(int j=min(b,);j<=b;j++){
zu[].num++;
int c=zu[].num;
zu[].w[c]=zu[].w[i]+zu[].w[j];
zu[].v[c]=zu[].v[i]+zu[].v[j];
}
}
return;
}
int main()
{
init();
scanf("%d",&t);
while(t--)
{
memset(dp,,sizeof(dp));
scanf("%d%d",&n,&m);
string ss,w,v;
int a,b;
for(int i=;i<=n;i++){
cin>>ss>>a>>b;
int id=mp[ss];
zu[id].num++;
int c=zu[id].num;
zu[id].v[c]=a;
zu[id].w[c]=b;
}
combine_finger();
combine_two();
memset(dp,-,sizeof(dp));
dp[][]=;
for(int k=;k<=;k++){
for(int i=;i<=m;i++){
dp[k][i]=max(dp[k][i],dp[k-][i]);
if(dp[k-][i]==-)
continue;
for(int j=;j<=zu[k].num;j++){
int min1=min(m,i+zu[k].w[j]);
dp[k][min1]=max(dp[k][min1],dp[k-][i]+zu[k].v[j]);
}
}
}
cout<<dp[][m]<<endl;
}
return ;
}