[文章目录]
Description
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。” 如果你是辰辰，你能完成这个任务吗？
妈呀，显然不是01背包能过得了的，不过一看v，t，都是<=10的，所以最多只有100种背包，（嘻嘻嘻）累加num再拆包就好了。时间过得去了
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int m,n,num[20][20],f[101000];
int main()
{
scanf("%d%d",&n,&m);
for(int x,y,i=1;i<=n;i++)
{
scanf("%d%d",&x,&y);
num[x][y]++;
}
for(int i=1;i<=10;i++)
{
for(int j=1;j<=10;j++)
{
//printf("%d ",num[i][j]);
int tmp=1;
while(num[i][j]>=tmp)
{
num[i][j]-=tmp;
for(int k=m;k>=i*tmp;k--)
{
f[k]=max(f[k],f[k-tmp*i]+j*tmp);
}
tmp<<=1;
}
if(num[i][j])
{
tmp=num[i][j];
for(int k=m;k>=tmp*i;k--)
{
f[k]=max(f[k],f[k-tmp*i]+j*tmp);
}
}
}
//puts("");
}
printf("%d",f[m]);
return 0;
}