【题解 && 单调队列优化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
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30