【题解 单调队列优化dp】 简单的加法乘法计算题

本文主要是介绍【题解 单调队列优化dp】 简单的加法乘法计算题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：

---

分析：

由于对于每一步而言，我们都需要的是最小步数
所以我们很显然的可以写出一个dp方程：
设$f[i]$表示达到i时的最小步数
我们有两种操作，也就是说我们可以通过一下两种方式转移过来：
$f[i]=min(f[i-1],f[i-2]\dots \dots ,f[i-n]+1)$
$f[i]=min(f[i/a[j]]+1,f[i])$

对于第二种方式，由于m最大只有10，所以我们可以暴力转移
那么对于第一种方式，我们发现这是一段长度固定区间里的最小值
我们可以考虑滑动窗口，即单调队列去优化dp
线段树常数太大，会t，不建议使用

---

Code

#include<bits/stdc++.h>
using namespace std;const int N = 5e6+100;int y,n,m;
int q[N],h,t;
int a[N],f[N];int main(){scanf("%d %d %d",&y,&n,&m);for (int i = 1; i <= m; i++) scanf("%d",&a[i]);f[0] = 0;for (int i = 1; i <= n; i++) f[i] = 1;t = 0 , h = 1;for (int i = 1; i <= n; i++){while (f[q[t]] > f[i] && h<=t) t--;q[++t] = i;}for (int i = n+1; i <= y; i++){while (i-q[h] > n && h<=t) h++;f[i] = f[q[h]]+1;for (int j = 1; j <= m; j++)if (i%a[j] == 0) f[i] = min(f[i],f[i/a[j]]+1);while (f[q[t]] > f[i] && h<=t) t--;q[++t] = i;}cout<<f[y];return 0;
}

这篇关于【题解 单调队列优化dp】 简单的加法乘法计算题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---