1. 题目

传送门= ̄ω ̄=

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

2. 题解

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

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

再单调队列一下就行了

abs的博客讲的很好了,我也不做过多赘述:https://www.k-xzy.xyz/?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;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *