HDU 3732 Ahui Writes Word 多重背包优化01背包

时间:2023-03-08 17:15:39
HDU 3732 Ahui Writes Word 多重背包优化01背包

题目大意:有n个单词,m的耐心,每个单词有一定的价值,以及学习这个单词所消耗的耐心,耐心消耗完则,无法学习。问能学到的单词的最大价值为多少。

题目思路:很明显的01背包,但如果按常规的方法解决时间复杂度O(n)=1e9,会超时。因为每个单词的价值和代价都不超过10,所以可以用二维数组G[V][W],记录价值为V,代价为W的单词的个数,并用多重背包的思路解决。

#include<cstdio>
#include<stdio.h>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#define INF 0x3f3f3f3f
#define MAX 100005
#define mod 1000000007 using namespace std; int dp[MAX],val[MAX],w[MAX],G[][];
char str[MAX]; int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(G,,sizeof(G));
memset(dp,,sizeof(dp)); for(int i=; i<n; i++)
{
scanf("%s",str);
scanf("%d%d",&val[i],&w[i]);
G[val[i]][w[i]]++;
} for(int i=; i<=; i++) //价值
{
for(int j=; j<=; j++) //代价
{
int k=;
while(k < G[i][j])
{
for(int q=m; q>=j*k; q--)
{
dp[q]=max(dp[q],dp[q-j*k]+i*k);
}
G[i][j]-=k;
k*=;
}
k=G[i][j];
for(int q=m; q>=j*k; q--)
{
dp[q]=max(dp[q],dp[q-j*k]+i*k);
}
}
}
printf("%d\n",dp[m]);
}
return ;
}