怎么分组呢?题解区有人用“插入排序”,
我用链表,结果超时,样例过了,得0分
#include<iostream>
#include<cstring>
using namespace std;
struct
{
int v,t,s,w;
}post[104];
int f[101][101]={0};
int next[200];//链表连接线
int nv[200];//链表内容域:美观度为某值的物品号
int vex[101];//美观度为某值的链表头
int main()
{
int n,m,t;
int i,j,k,l;
int minv=2000000000;
int maxv=0;
int cnt=0;//链表计数器
int temp,now;
cin>>n>>m>>t;
memset(vex,-1,sizeof(vex));//初始化链表尾标志
for(i=1;i<=n;i++)
{ cin>>post[i].v>>post[i].t>>post[i].s>>post[i].w;
cnt++; nv[cnt]=i; next[cnt]=vex[post[i].v]; vex[post[i].v]=cnt;//链表插入
minv<?=post[i].v; maxv>?=post[i].v;
}
for(i=minv;i<=maxv;i++)//枚举美观度
for(j=m-1;j>=0;j--)//分组背包 体力维
for(k=t;k>=0;k--)//时间维
{
temp=vex[i];//链表指针
while(temp!=-1)//链表到头
{
now=nv[temp];//可用物品号
if(j>=post[now].s&&k>=post[now].t)
f[j][k]>?=f[j-post[now].s][k-post[now].t]+post[now].w;
temp=next[temp];//链表指针移动
}
}
cout<<f[m-1][t];
getchar();
getchar();
getchar();
getchar();
return 0;
}