Problem
poj.org/problem?id=1742
Reference
www.cppblog.com/flyinghearts/archive/2010/09/01/125555.html
blog.csdn.net/wangjian8006/article/details/7606917
题意
分别给出 n 种面值为 ai 的硬币 ci 个，问用这些硬币可以组成的 [ 1， m ] 中的多少种金额。
Analysis
多重背包。按平常的二进制优化也能过，不过要把调用 max() 改成用 if 来判断…
之前以为可能是普通的二进制优化复杂度太高，所以要用单调队列的优化方法。于是去学了一发单调队列优化（第一个参考博客）。
为了好看，我把单调队列封装起来用，结过超时了…
然后我学参考博客的写法，不用封装的队列，还是超时了…
无奈，不用单调队列的通用模板。看它下面的多重背包特例和第二个参考博客。
bool dp[i]：金额 i 是否能被凑出。
num[i]：凑出金额 i 要消耗当前这种硬币的数量（考每一种硬币时都要先清零）
状态转移：if ( !dp[j] && dp[ j-a[i] ] && num[ j-a[i] ] < c[i] ) { dp[j] = true; num[j] = num[ j-a[i] ] + 1; }
Source code
普通二进制优化（Accepted，但比较慢）
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 100, M = 100000;
int a[N], c[N], dp[M+1];
void zero_one(int v, int m)
{
for(int j=m; j>=v; --j)
if(dp[j] < dp[j-v] + v)
dp[j] = dp[j-v] + v;
}
void complete(int v, int m)
{
for(int j=v; j<=m; ++j)
if(dp[j] < dp[j-v] + v)
dp[j] = dp[j-v] + v;
}
int main()
{
int n, m;
while(~scanf("%d%d",&n,&m) && (n||m))
{
for(int i=0; i<n; ++i)
scanf("%d", a+i);
for(int j=0; j<n; ++j)
scanf("%d", c+j);
memset(dp, 0, sizeof dp);
for(int i=0; i<n; ++i)
if(a[i] * c[i] > m)
complete(a[i], m);
else
{
for(int k=1; c[i]>=k; c[i]-=k, k<<=1)
zero_one(a[i]*k, m);
if(c[i])
zero_one(a[i]*c[i], m);
}
int cnt = 0;
for(int i=1; i<=m; ++i)
if(dp[i] == i)
++cnt;
printf("%d\n", cnt);
}
return 0;
}
封装单调队列（TLE，备份一下写法）
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 100, M = 100000;
int arr[M+1], a[N], c[N], dp[M+1];
// Humdrum Queue
struct hq
{
int *buf, *head, *tail;
hq(int *h): buf(h), head(h), tail(h-1) {}
void clear()
{
head = buf;
tail = buf - 1;
}
void push(int x)
{
while(head<=tail && *tail<x)
--tail;
*++tail = x;
}
void pop()
{
++head;
}
int top() const
{
return *head;
}
} dui(arr);
void pack(int i, int m)
{
if(!a[i] || !c[i])
return;
else if(c[i] == 1) // 0/1背包
for(int j=m; j>=a[i]; --j)
dp[j] = max(dp[j], dp[j-a[i]] + a[i]);
else if(a[i] * c[i] > m) // 完全背包
for(int j=a[i]; j<=m; ++j)
dp[j] = max(dp[j], dp[j-a[i]] + a[i]);
else
{
for(int r=0; r<a[i]; ++r) // 枚举余数
{
queue<int> que; // 普通队列，装所有可能的候选项
dui.clear(); // 单调队列，将候选项排成但调递减
for(int j=r, k=0, t; j<=m; j+=a[i], ++k)
{
if(que.size() == c[i])
{
if(que.front() == dui.top())
dui.pop();
que.pop();
}
t = dp[j] - k * a[i];
que.push(t);
dui.push(t);
dp[j] = dui.top() + k * a[i];
}
}
}
}
int main()
{
int n, m;
while(~scanf("%d%d",&n,&m) && (n||m))
{
for(int i=0; i<n; ++i)
scanf("%d", a+i);
for(int j=0; j<n; ++j)
scanf("%d", c+j);
memset(dp, 0, sizeof dp);
for(int i=0; i<n; ++i)
pack(i, m);
int cnt = 0;
for(int i=0; i<=m; ++i)
if(dp[i] == i)
++cnt;
printf("%d\n", cnt);
}
return 0;
}
不封装单调队列（TLE，也是备份写法）
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 100, M = 100000;
int a[N], c[N], dp[M+1];
int org[M+1], *oh, *ot; // origin queue, origin-head, origin-tail
int hq[M+1], *hh, *ht; // humdrum queue, ...
void pack(int i, int m)
{
if(!a[i] || !c[i])
return;
else if(c[i] == 1)
for(int j=m; j>=a[i]; --j)
dp[j] = max(dp[j], dp[j-a[i]] + a[i]);
else if(a[i] * c[i] > m)
for(int j=a[i]; j<=m; ++j)
dp[j] = max(dp[j], dp[j-a[i]] + a[i]);
else
{
for(int r=0; r<a[i]; ++r)
{
oh = org, ot = org - 1;
hh = hq, ht = hq - 1;
for(int j=r, k=0, t; j<=m; j+=a[i], ++k)
{
if(ot == oh + c[i])
{
if(*oh == *hh)
++hh;
++oh;
}
t = dp[j] - k * a[i];
*++ot = t;
while(ht>=hh && *ht<t)
--ht;
*++ht = t;
dp[j] = *hh + k * a[i];
}
}
}
}
int main()
{
int n, m;
while(~scanf("%d%d",&n,&m) && (n||m))
{
for(int i=0; i<n; ++i)
scanf("%d", a+i);
for(int j=0; j<n; ++j)
scanf("%d", c+j);
memset(dp, 0, sizeof dp);
for(int i=0; i<n; ++i)
pack(i, m);
int cnt = 0;
for(int i=1; i<=m; ++i)
if(dp[i] == i)
++cnt;
printf("%d\n", cnt);
}
return 0;
}
打标记+计数的方法（Accepted）
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100, M = 100000;
int a[N], c[N], num[M+1];
bool dp[M+1];
int main()
{
int n, m;
while(~scanf("%d%d",&n,&m) && (n||m))
{
for(int i=0; i<n; ++i)
scanf("%d", a+i);
for(int j=0; j<n; ++j)
scanf("%d", c+j);
memset(dp, false, sizeof dp);
dp[0] = true;
for(int i=0; i<n; ++i)
{
memset(num, 0, sizeof num);
for(int j=a[i]; j<=m; ++j)
if(!dp[j] && dp[j-a[i]] && num[j-a[i]]<c[i])
{
dp[j] = true;
num[j] = num[j-a[i]] + 1;
}
}
int cnt = 0;
for(int i=1; i<=m; ++i)
cnt += dp[i];
printf("%d\n", cnt);
}
return 0;
}
