POJ 1276 Cash Machine (多重背包&單調隊列)

http://poj.org/problem?id=1276

模闆題。

完整代碼：

/*110ms,4316KB*/

#include<cstdio>
#include<cstring>
const int mx = 1005;
const int mxw = 1000005;

int w[mx], m[mx], dp[mxw], deq[mxw], deqv[mxw];

int solve(int maxw, int n)
{
	memset(dp, 0, sizeof(dp));
	int i, a, j, s, t, val;
	for (i = 0; i < n; ++i)
		for (a = 0; a < w[i]; ++a)///枚舉a=j%w[i]
		{
			s = t = 0; ///deque的頭和尾
			for (j = 0; j * w[i] + a <= maxw; ++j)
			{
				val = dp[j * w[i] + a] - j * w[i];///劃歸為可重複使用的值
				while (t > s && deqv[t - 1] <= val) --t;///保證deque的隊首是最大的
				deq[t] = j;
				deqv[t++] = val;
				dp[j * w[i] + a] = deqv[s] + j * w[i];///從雙端隊列的頭部取出最大值
				if (deq[s] == j - m[i]) ++s;///這一頭部已無法使用
			}
		}
	return dp[maxw];
}


int main()
{
	int maxw, n, i;
	while (~scanf("%d%d", &maxw, &n))
	{
		for (i = 0; i < n; ++i)
			scanf("%d%d", &m[i], &w[i]);
		printf("%d\n", solve(maxw, n));
	}
	return 0;
}
           

附：相似題目

HDU 2191 悼念512汶川大地震遇難同胞——珍惜現在，感恩生活