P8357
AzusaShirasu
·
·
题解
理解题意后，不难发现一个事实：可以把硬币分成两堆称，然后合并起来。容易证明这是无后效性的。
所以就能根据题意推出方程。设 f_i 表示 i 个硬币中找假币的最小代价，有：
f_x=\operatorname{min}_{i=1}^{x-1}\{f_i+ai+b\lceil\frac{x}{i}\rceil\}
根据这个式子算就好了。但是这样 1D/1D 的转移是 O(n^2) 的，过不去。优化？单调队列似乎不适用于这题。
正解是找性质：发现转移的时候出现 b\lceil \frac{x}{i} \rceil，熟悉整除分块套路的都知道可以对 x-1 做整除分块。然后就显然了：对于每一块，取最左端点肯定是最优的。所以转移的时候只要转移每一块的左端点即可。
$$v(x)=\begin{cases}
x & x\leq\lfloor\frac{n-1}{x}\rfloor\\
k+\lfloor\frac{n-1}{x}\rfloor & x>\lfloor\frac{n-1}{x}\rfloor
\end{cases}$$
$k$ 是一个常数，取值范围大约在 $[\sqrt n,\inf)$，官方取的是 $10^5$。
有没有更优美的做法？其实有：C++ pbds 里有一个比 `unordered_map` 效率更高的容器 `hash_table`，用哈希值存储元素，平均下是 $O(1)$ 的。使用方式：
- 头文件（有两个）：
```cpp
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
```
- 命名空间：`using namespace __gnu_pbds;`。
- 声明方式：有两种哈希表：
```cpp
cc_hash_table<int,int> cc;//链表
gp_hash_table<int,int> gp;//开放寻址
```
一般开放寻址会快一点，效率瓶颈主要是在处理哈希冲突的方式上。虽然如此，由于这题的特殊性质，使用链表哈希表会更快一些（最慢测试点比开放寻址法快了约 500ms）。
然后就可以用记忆化搜索通过本题了。略微卡常后最慢的点能跑进 $0.8$ 秒，也算是稳定的了。
```cpp
#include<bits/stdc++.h>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
// 省略快读模板
using namespace fastio;
ll n,a,b;
cc_hash_table<ll,ll> gp;//关键
cc_hash_table<ll,ll> pre;//关键
ll dp(ll x){
auto at=gp.find(x);
if(at!=gp.end())return at->second;
ll ans=0x7fffffffffffffffll;
ll N=x-1,p;
for(ll L=1,R;L<=N;L=R+1){//整除分块
R=N/(N/L);
ll cur=dp(L)+(N/L+1)*b+x*a;
if(cur<ans)ans=cur,p=L;
}
pre[x]=p;
return gp[x]=ans;
}
const int maxn=10000000+5;
ll path[maxn],loc;
int main(){
cin>>n>>a>>b;
gp[1]=0,dp(n);
int cur=n,v;
while(v=pre[cur])path[++loc]=v,cur=v;
wr(gp[n],' '),wr(loc);//wr 是快读输出函数
for(int i=1;i<=loc;i++)wr(path[i],' ');
io::flush();//快读刷新缓冲区
return 0;
}
```