单调队列优化AC代码(O2优化):

#include <iostream>
#include <algorithm>
#include <deque>
#include <cstring>
using namespace std;
deque<int> q;
const int size = 10005;
long long dp[size],bp[size];
long long v,w,d,n,m,C,a,b,c;
int main()
{
	cin >> n >> m >> C;
	for(long long i = 1;i <= n;i++)
	{
		memcpy(bp,dp,sizeof(dp));
		cin >> v >> w >> d;
		//     体积 价值  数量 
		if(d >= C / v)
		{
			for(long long j = v;j <= C;j++)
				dp[j] = max(dp[j],dp[j - v] + w);
		}
		else
		{
			for(long long j = 0;j < v;j++)
			{
			q.clear();
			for(long long k = j;k <= C;k += v)
			{
				if(!q.empty() && q.front() < k - d * v)
					q.pop_front();
				if(!q.empty())
					dp[k] = max(bp[k],bp[q.front()] + (k - q.front()) / v * w);
				while(!q.empty() && bp[k] >= bp[q.back()] + (k - q.back()) / v * w)
					q.pop_back();
				q.push_back(k);
			}
			}
		}
		
	}
	
	long long y = 0;
	for(long long i = 1;i <= m;i++)
	{
		cin >> a >> b >> c;
		for(long long j = C;j >= 0;--j)
			for(long long x = 0;x <= j;x++)
			{
				y = a * (x * x) + b * x + c;
				dp[j] = max(dp[j],dp[j - x] + y);
			}
	}
	cout << dp[C] << endl;
	return 0;
}

二进制优化AC代码:

#include <iostream>
#include <algorithm>
using namespace std;
const int size = 10005;
long long dp[size];
long long n,m,C,num_v[size],num_w[size],num_d[size],v,w,d,a,b,c;
int main()
{
	cin >> n >> m >> C;
	long long num = 0;
	for(long long i = 1;i <= n;i++)
	{
		cin >> v >> w >> d;
		if(d >= C / v)
		{
			for(long long j = v;j <= C;j++)
				dp[j] = max(dp[j],dp[j - v] + w);
		}
		else
		{
			for(long long j = 1;j <= d;j <<= 1)
			{
				d -= j;
				num_v[++num] = v * j;
				num_w[num] = w * j;
				num_d[num] = 1;
			}
			if(d > 0)
			{
				num_v[++num] = v * d;
				num_w[num] = w * d;
				num_d[num] = 1;
				d = 0;
			}
		}
	}
	
	for(long long i = 1;i <= num;i++)
		for(long long j = C;j >= num_v[i];j--)
			dp[j] = max(dp[j],dp[j - num_v[i]] + num_w[i]);
	
	//处理奇货 
	long long y = 0;
	for(long long i = 1;i <= m;i++)
	{
		cin >> a >> b >> c;
		for(long long j = C;j >= 0;--j)
			for(long long x = 0;x <= j;x++)
			{
				y = a * (x * x) + b * x + c;
				dp[j] = max(dp[j],dp[j - x] + y);
			}
	}
	cout << dp[C] << endl;
	return 0;
}

此题题解中大部分人都在强调常数优化,是因为他们大部分没有看到 当一个物品的数量大于 总容量/该物品体积时, 这个物品可以当做完全背包来做,完全背包比多重背包快多少就不用我说了吧,他们没有看到这一点,但发现自己的代码只差那么几ms就可以AC,于是就花了大量精力在所谓的常数优化上来强过这道题.实际上,我的二进制优化朴素代码就完全可以过去,使用STL中的deque,开氧气优化也过得去.