T1.Coins(POJ1742)

多重背包最基本的状态转移方程是这样的： 用 f[i][j] 表示前 i 个物品装进背包占容量为 j 时的最大价值。
$$

题意：

求用 n 种硬币每种 c[i] 个最多可以凑出多少种面额？

二进制优化:

作为将 $O(NV\sum{\frac{V}{w[i]}})$也就是 $O(N^2V)$级别的算法优化成 $O(V\sum{log(c[i])})$的方法，自然少不了对”2″ 灵活的应用。
由于这种方案的优化效果不是非常好，无法顺利通过本题，而且大家肯定已经可以熟练运用，这里暂不讨论。

---

单调队列优化：

$O(K\times logN)$的算法再经过某些基于单调性的脑洞级优化后，会变成惊人的 $O(K\times 1)$而这道题用到的当然就是这种方法。
观察 f[i][j] 是由哪些东西的最小值转移过来的：

所以，对于这道题，我们要知道的就是红色格子里有没有可以达到的容量。而红色格子是连续的最多 c[i] 个。
这不是 so-easy 的东西吗？

下面具体介绍几种解决方法：

1.

我们建立一个假的队列，这个队列有队首和队尾，但是没有队列元素。
现在我们从 f[i-1][0] 向 f[i-1][j] 每隔 w[i] 个将那个数添加到队列中，用队列记录队首到队尾的和。这样对于 f[i][j]，队列中的所有元素的和就是我们图片中红色格子的和。

2.

不用建立队列，并且将方程的维数降为 1 维。这时转移方程就是：（f[j] 表示达成 j 容量的方案数。）

for(int i=1;i<=n;i++)
{
    for(int j=v[i];j<=V;j++)
        f[j]=f[j]+f[j-v[i]];
    for(int j=v[i];j<=V;j++)
        if(j-(c[i]+1)*w[i]>=0)f[j]-=f[j-(c[i]+1)*w[i]];
}

这就是完全背包的做法再减去不应该装的物品的做法。程序结束后 f[i] 数组里留下来的就是达成 i 容量的方案数。但是由于第二层循环需要 2 次，这种方法还是会莫名其妙就 TLE。。。

3.

借鉴于第二种方法，我们可以再开辟一个数组 s[j] 表示 f[j] 是装了多少件 i 物品从而变为可行的。总之这样就可以 AC

for(srg int i=1;i<=n;i++)
{
    memset(s,0,sizeof(s));
    for(srg int j=v[i];j<=mv;j++)
    {
        if(!f[j]&&f[j-v[i]]&&s[j-v[i]]<c[i])
        {
            ++tot;
            f[j]=1;
            s[j]=s[j-v[i]]+1;
        }
    }
}

那么我通过此题的代码如下：(应用了诸多卡常技巧)

#include <iostream>
#include <cstdio>
#include <cstring>

#define MX 110
#define srg register

using namespace std;

int v[MX],c[MX];
int f[100010];
int s[100010];
int n,mv,tot;

int main()
{
    while(scanf("%d %d", &n, &mv) && n && mv >= 0)
    {
        for(srg int i=1;i<=n;i++)scanf("%d",&v[i]);
        for(srg int i=1;i<=n;i++)scanf("%d",&c[i]);
        for(srg int i=0;i<=mv;i++)f[i]=0;
        f[0]=1,tot=0;
        for(srg int i=1;i<=n;i++)
        {
            memset(s,0,sizeof(s));
            for(srg int j=v[i];j<=mv;j++)
                if(!f[j]&&f[j-v[i]]&&s[j-v[i]]<c[i])
                    ++tot,f[j]=1,s[j]=s[j-v[i]]+1;
        }
        printf("%d\n",tot);
    }
    return 0;
}

---

T2. 多重背包 (HDU2191)

题意：

给定一些物品的价值、大小、数量。求一个大小为 m 的背包最多装得下多少价值的物品。

虽然这道题乱搞都可以 AC，但是我们还是实用单调队列优化

这里的 f[i] 表示容量为 i 的背包可以装下的最大价值 (而不是恰好装下)。因此可以很方便地使用单调队列优化
这所谓的单调队列是神码样的呢？它其实维护了两个单调性：
右边的比左边的新进队。
左边的比右边的优。
为什么这样就对呢？其他单调性为什么不对呢？
这样想：我们至少得维护时间的单调性：也就是右边的比左边的新进队。为什么同时左边的要比右边的优呢？感性地想：在队列中的元素向左侧 “流动” 时，我们会 “失去” 非常优秀的解而只能从新进来的解中转移。因此单调性是左边优于右边。
有了单调队列的思路，有了状态转移方程，我们就可以轻松的写出代码。
噢，不知道大家有没有想到这样一个问题：
由于状态转移方程是：
f[i]=max(f[i-kw[i]]+kv[i])
我们不能直接将每个 f[i] 的值存进队列，而应该保存 f[i]-i/w[i]*v[i]（仔细想一想为什么）
有了以上这些准备工作，我们的程序差不多就完备了。

#include <iostream>
#include <cstdio>
#include <cstring>

#define max(a,b) ((a>b)?(a):(b))
#define MX 101

using namespace std;

int v[MX],w[MX],c[MX];
int n,m;

void input()
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d%d",&w[i],&v[i],&c[i]);
}

pair<int,int>q[MX];
int h,t;
int f[MX];

void work()
{
    int relex;
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++)
    {
        if(c[i]==0)continue;
        if(c[i]>m/w[i])c[i]=m/w[i];
        for(int j=0;j<w[i];j++)
        {
            h=0,t=1;
            for(int k=0;k*w[i]+j<=m;k++)             //这里我们直接枚举装入几个物品，而不是枚举装到多大空间。
            {
                relex=f[k*w[i]+j]-k*v[i];                      //要减去 k*v[i], 详见上文的分析
                while(q[h].first<relex&&h>=t)h--;
                q[++h].first=relex;
                q[h].second=k;
                while(q[t].second<k-c[i])t++;
                f[k*w[i]+j]=q[t].first+k*v[i];
            }
        }
    }
    printf("%d\n",f[m]);
}

int main()
{
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
        input();
        work();
    }
    return 0;
}

---

T3.Bank notes(BZOJ1531 权限题)

题意：

给定一些面值的硬币和它们的数量，求凑成给定面值的最少硬币数为多少。

单调队列：

经过像 T2 那样严谨的分析，我们得出：我们需要一个单调队列维护以下单调性：
队列右侧比左侧新进入
队列左侧的元素代表的凑成的硬币数要更少
这样我们就就可以得到一份优美的代码

#include <iostream>
#include <cstring>
#include <cstdio>

#define MX 201

using namespace std;

int n,mv;
int v[MX],c[MX],f[20001];

void input()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&v[i]);
    for(int j=1;j<=n;j++)scanf("%d",&c[j]);
    scanf("%d",&mv);
}

pair<int,int> q[20001];
int h,t;

void work()
{
    int rx;
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<v[i];j++)
        {
            h=0,t=1;
            for(int k=0;k*v[i]+j<=mv;k++)
            {
                rx=f[k*v[i]+j]-k;
                while(q[h].first>rx&&h>=t)h--;
                q[++h]=make_pair(rx,k);
                while(q[t].second<k-c[i]&&h>=t)t++;
                f[k*v[i]+j]=q[t].first+k;
            }
        }
    }
    printf("%d\n",f[mv]);
}

int main()
{
    input();
    work();
    return 0;
}