转自：http://hi.baidu.com/billdu/item/54bde13de63134be134b1400
题目大意：给你N（1 ≤ N ≤ 100）种钞票以及拥有的张数，以及一个给定的值M（1 ≤ M ≤ 100,000 ）。你需要统计出用这些钞票能够凑出来的钱数，在1 - M的范围中有多少个。
楼教主的“男人八题”之一。作为男人八题，那么当然要难一点才有男人的味道，所以说applepi为了成为真男人，在这个题上TLE了10回……不多扯了。多重背包问题，通常采用的方法一般都是二进制拆包，时间复杂度O(VNlogM)。然而，这个题正是BT到这样的时间复杂度过不了的地步。所以说，有必要采用更高级的方式，那就是单调队列。实际上，多重背包的单调队列是我见过的比较麻烦的一种。
众所周知，若用dyna[i][j]表示背包容量为j，物品数为i的最大价值，多重背包的状态转移方程是
dyna[i][j] = max{ dyna[i - 1][j - k * w[i]] + k * c[i] } (0 ≤ k ≤ s[i])
k, c, s分别表示物品的费用，价值和数量。
直接这样上的话，复杂度可是O(VNM)。所以说考虑到方程“向前找”的特性，可以用单调队列来优化状态转移。
首先，单调队列中存放的是前面的价值和容量。为什么还要把容量存进去呢？我们把方程变个形看看：
dyna[i][j] = max{ dyna[i - 1][place] + (j - place) / w[i] * c[i] } (place >= j - w[i] * s[i])
dyna[i - 1][place]的值永远都不会变，但是根据place的不同，在dyna[i][j]处所能转移到的值也不一样。所以说必须把容量也存进去才能正确转移。
按照单调队列的特性，每次把新的dyna[i - 1][j - k * w[i]]的值进队，把老的值出队，之后取首个元素就可以了。然而循环的时候顺序要改变，如果要使用单调队列，循环的步长一定是w[i]。那么与首元素对w[i]取模的值不一样的元素就不能更新。要解决这个问题很简单——只需要用两个循环就可以了。模式如下：
for (j = 0; j < w[i]; j++)
{
for (k = j; k <= m; k += w[i])
{
// 状态转移
}
}
至此这个问题就基本解决了。然而，单纯的O(VN)的多重背包要过这个题还是有点困难，必须进一步优化才可以。这就是各位尚未AC的看官的任务了——男人嘛，一定要自己解决最麻烦的地方。实在是难以解决的，discuss里面有一个解决方案，诸位不妨一试。看一下applepi的代码也可以。
代码如下：
#include <stdio.h>
#define max(a,b) ((a)>(b)?(a):(b))
char dyna[100010];
int dqueue[100010], pl[100010], head, tail;
int w[110], s[110], n, m;
int main ()
{
int i, j, k, l, maxi, ans;
while (1)
{
scanf("%d %d", &n, &m);
if (n == 0 && m == 0) break;
for (i = 1; i <= n; i++)
scanf("%d", &w[i]);
for (i = 1; i <= n; i++)
scanf("%d", &s[i]);
memset(dyna, 0, sizeof(dyna));
dyna[0] = 1;
for (i = 1; i <= n; i++)
{
maxi = w[i] * s[i];
if (s[i] == 1)
{
for (j = m; j >= w[i]; j--)
dyna[j] = max(dyna[j], dyna[j - w[i]]);
}
else if (maxi < m)
{
for (j = 0; j < w[i]; j++)
{
head = tail = 0;
for (k = j; k <= m; k += w[i])
{
if (tail != head) { if (k - pl[head] > maxi) head++; }
if (dyna[k])
{
dqueue[tail] = dyna[k];
pl[tail] = k; tail++;
}
else if (tail != head) dyna[k] = 1;
}
}
}
else
{
for (j = w[i]; j <= m; j++)
dyna[j] = max(dyna[j], dyna[j - w[i]]);
}
}
ans = 0;
for (i = 1; i <= m; i++)
if (dyna[i]) ans++;
printf("%d\n", ans);
}
return 0;
}