题意

warma付钱的决策是多重背包模型，收银员找零是完全背包模型，先预处理，然后从w开始枚举S，求min即可

多重背包不开二进制优化应该会挂，开了优化可能没有推出结论也可以水过去

解法

20分

骗分大法直接输出-1

80分

写在前面

本题改编自USACO-The Fewest Coins，仅扩大了部分数据范围

题目描述

除夕之夜，warma唱完鼠来宝之后从国正中心出来，在寒风中瑟瑟发抖，于是乎决定去金拱门奢侈一把。

吃饭全靠赚赏（sang）钱的warma兜里只有硬币，为了快点吃上饭，她想让硬币转手的次数尽可能最少，即付出去的硬币数与找零得到的硬币数之和（S）最小。

市面上流通的硬币共有n（1<=N<=10000）种，面值分别为$v_1,v_2,...,v_n$（$1<=V_i<=120$)。对于面值为$v_i$的硬币，warma分别有$c_i$个（$0<=c_i<=10000$）。同时，出于囊中羞涩，warma只打算购买总价值为$w$（1<=w<=10000）的食物和（谢拉）小伙伴们分享。

特别要注意的是，金拱门是国际品牌，各种硬币都很充足，可以满足任意的找零方案。收银员小姐姐也很善解人意，听到warma的要求后，决定用最少的硬币为warma找零

作为只会吹灭火器的音乐（le）人，warma找到了经验丰富的你（你也要过饭？），希望你能帮她算出付出去的硬币数与找零得到的硬币数之和（S）最小是多少。

前言

背包问题一直是DP的经典模型，但是像我这样的菜鸡总是学不会（再聪明一点~）所以综合之前的做题和听课，把自己的一点感悟记录下来。（大部分与背包九讲一致）

01背包

01背包是背包模型的基础，也是我DP入门的噩梦，那就从这个问题入手吧。

题目

N件物品和一个容量为V的背包，每件物品有一个体积为c，有一个价值为v。求解背包能装入最大的价值总和。

思路

状态表示：$f[i][j]$表示前i件物品放入容量为j的背包所能获得的最大价值和

状态计算：

• 状态转移方程：$f[i][j]=max(f[i-1][j], \\f[i-1][j-c[i]]+v[i])$
• 初始状态：$f[i][0]=0,f[0][j]=0$
• 边界条件：$j<c[i]$时，$f[i][j]=f[i-1][j]$

写在前面

二分答案和差分构造上我一直是苦手，写这一篇存档记录一下可用的模板。

Problem1

描述：

给定升序排列数组$a[n]$以及$q$个查询，每次查询$k$在数组中的起始位置。

题解：

二分查找，贴一个模板还有一个暴力(前者45ms，后者39ms)

写在前面

还有一个月就要蓝桥杯省赛了，复习的时候顺便总结一下。题目题解主要参考《算法竞赛进阶指南》以及acwing

Problem1

描述：从1~n选任意个，输出全部选择方案

题解：每个数只有选和不选两种状态，通过dfs访问到$2^n-1$个选择方案。

写在博客最前面

几经折腾，这个博客终于生出来了（？）

感谢ketchup学长的催更（bushi，感谢next，感谢hexo，感谢nodejs，感谢所有本博客中引用到的模块的开发者们（鞠躬）。这两天倒腾博客的时候遇到了不少的坑，一并在这里记录下来，之后会持续更新（大概？

Next主题改造计划

分享按钮和标签

文章页中，如果开启了标签页和分享按钮，就会出现标签在上，分享按钮在下的尴尬局面，再加上全文结束的分隔行就会显得文章的尾部十分拖沓，所以就稍微加了一些自定义css，试图将两者放到一行内，代码如下：