cogs 53 多人背包

/*
要求每个最优 即累加前k优解
注意不用去重
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 210
#define maxm 5010
#define maxk 60
using namespace std;
int n,m,k,w[maxn],v[maxn],f[maxm][maxk];
int x[maxk],y[maxk],a,b,z,ans;
int init()
{
int x=0;bool f=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
if(f)return -x; return x;
}
int main()
{
//freopen("bags.in","r",stdin);
//freopen("bags.out","w",stdout);
k=init();m=init();n=init();
for(int i=1;i<=n;i++)
w[i]=init(),v[i]=init();
memset(f,128,sizeof(f));
f[0][1]=0;
for(int i=1;i<=n;i++)
{
for(int j=m;j>=w[i];j--)
{
for(int l=1;l<=k;l++)
{
x[l]=f[j][l];
y[l]=f[j-w[i]][l]+v[i];
}
a=b=z=1;
x[k+1]=y[k+1]=-1;
while(z<=k&&(x[a]!=-1||y[b]!=-1))
{
if(x[a]>y[b])f[j][z]=x[a],a++;
else f[j][z]=y[b],b++;
z++;
}
}
}
for(int i=1;i<=k;i++)
ans+=f[m][i];
printf("%dn",ans);
return 0;
}