1. 题目

注：这是个权限题。。。不过用博客上的 bzoj 离线版可以看到题目

2. 题解

单调队列优化多重背包模板题。。。
（我这么弱只做的动模板题了）

朴素的递推式是： $f_x=min\{f_{x-b_i\times k}+k\} ,k\in [1,c_i]$

再单调队列一下就行了

abs 的博客讲的很好了，我也不做过多赘述：https://www.mina.moe/?p=2009

代码：

#include <bits/stdc++.h>
using namespace std;
int n,m,b[205],c[205],q1[20005],q2[20005],f[20005],top,end;
int main()
{
    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),memset(f,127,sizeof(f)),f[0]=0;
    for(int i=1;i<=n;i++)
        for(int j=0;j<b[i];j++)
        {
            top=end=1;
            for(int k=j;k<=m;k+=b[i])
            {
                while(top<end&&q2[top]<k-c[i]*b[i])top++;
                while(top<end&&f[k]<=q1[end-1]+(k-q2[end-1])/b[i])end--;
                q1[end]=f[k],q2[end++]=k,f[k]=min(f[k],q1[top]+(k-q2[top])/b[i]);
            }
        }
    printf("%d\n",f[m]);
    return 0;
}

【题解】Bank notes 多重背包单调队列优化 BZOJ – 1531

于2017年7月20日2017年7月20日由XZYQvQ发布

1. 题目

2. 题解

XZYQvQ

0 条评论

发表回复取消回复

【题解】Bank notes 多重背包单调队列优化 BZOJ – 1531

于2017年7月20日2017年7月20日由XZYQvQ发布

1. 题目

2. 题解

XZYQvQ

0 条评论

发表回复 取消回复

发表回复取消回复