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

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

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

题目描述：

分析：

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