[bzoj1531][POI2005]Bank notes

Description

\(Byteotian\;Bit\;Bank(BBB)\) 拥有一套先进的货币系统,这个系统一共有\(n\)种面值的硬币,面值分别为\(b_1,b_2,...,b_n\).但是每种硬币有数量限制,现在我们想要凑出面值\(k\)求最少要用多少个硬币.

Input

第一行一个数\(n\).

第二行\(n\)个整数\(b_1,b_2,...,b_n\).

第三行\(n\)个整数\(c_1,c_2,...,c_n\),表示每种硬币的个数.

最后一行一个数\(k\),表示要凑的面值数量.

Output

一行一个数,表示最少需要付的硬币数.

Sample Input

3 
2 3 5 
2 2 1 
10

Sample Output

3

HINT

\(1\leq\;n\leq200,1\leq\;b_1
\(1\leq\;c_i\leq20000,1\leq\;k\;\leq20000.\)

Solution

\(f[i][j]\)表示用前\(i\)种硬币凑出价值\(j\)所需最少硬币数.

\(f[i][j]=min(f[i-1][j-b_i\;\times\;k]+k)\;(0\;\leq\;k\;\leq\;c_i)\)

对于对\(b_i\)取模结果相同的\(j\),可以用单调队列进行优化.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define N 205
#define M 20005
using namespace std;
int f[N][M],b[N],c[N],q[M],h,t,n,m;
inline void init(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&b[i]);
    for(int i=1;i<=n;++i)
        scanf("%d",&c[i]);
    scanf("%d",&m);
    for(int i=0;i<=n;++i)
        for(int j=1;j<=m;++j)
            f[i][j]=M;
    for(int i=1;i<=n;++i){
        for(int k=0;kc[i]) ++h;
                q[++t]=j;
                while(h