网站建设学那些课,网页界面设计体会,嵌入式软件开发笔试题,遵义网上办事大厅题目描述#xff1a; 分析#xff1a;
由于对于每一步而言#xff0c;我们都需要的是最小步数 所以我们很显然的可以写出一个dp方程#xff1a; 设 f [ i ] f[i] f[i]表示达到i时的最小步数 我们有两种操作#xff0c;也就是说我们可以通过一下两种方式转移过来#xff…题目描述 分析
由于对于每一步而言我们都需要的是最小步数 所以我们很显然的可以写出一个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
#includebits/stdc.h
using namespace std;const int N 5e6100;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] ht) t--;q[t] i;}for (int i n1; i y; i){while (i-q[h] n ht) 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] ht) t--;q[t] i;}coutf[y];return 0;
}
