题意
最快多少次才能够最快的得到$x^k$，可以从已经得到的数中乘除，最初只有x，比如 $x^31$,他最快可以通过通过6次操作
分析
1.为了能够知道当前搜索的解x是最优解，那么我能够做的就只有把比x小的解全部枚举一遍。所以就用到迭代加深搜索。
2.刚拿到这题，有很多种贪心策略，可惜后面发现都不对。然后试着用最短路的姿势来写，不过问题是你怎么才能确认这是最短路。这个搜索的空间无穷大，所以一直搜下去永远不能够确定。但这个就告诉我们不能把搜索空间弄的太深因为这样容易在某一个解空间里面无限搜下去，同时我们还要能确保当前搜到某一个解一定是最优解。由此，迭代加深搜索就凸现出来了
思考
1.对这类搜索复杂度一直很迷。而且有一个细节问题一直不能理解，为什么搜的时候一定要从当前最新的值a和前面的值进行运算得到新的值，而不能是以前的值b和c得出d，然后d和a再得出我想要的值呢？
2.搜的时候可以保留记录。以后对这类迷糊不确定上界的搜索首先就想到迭代加深吧！！！
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<stack>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<string>
#include<cmath>
using namespace std;
#define ll long long
#define rep(i,n) for(int i =0; i < n; ++i)
#define CLR(x) memset(x,0,sizeof x)
#define MEM(a,b) memset(a,b,sizeof a)
#define pr(x) cout << #x << " = " << x << " ";
#define prln(x) cout << #x << " = " << x << endl;
const int maxn = 4e5+100;
const int INF = 0x3f3f3f3f;
int a[20];
int des, depth;
int dis[maxn];
bool vis[maxn];
bool dfs(int pos) {
if(pos > depth) {
return false;
}
bool ok = false;
if(a[pos] == des) return true;
if(pos == depth) {
return a[pos] == des;
}
int ma = 1;
if(((a[pos] )<< (depth-pos)) < des) return false;
for(int i = 0; i <= pos; ++i){
a[pos+1] = a[pos] - a[i];
if(a[pos+1] > 0) {
ok = dfs(pos+1);
}
if(ok) return ok;
a[pos+1] = a[i] + a[pos];
if(a[pos+1] > 2*des+1) continue;
ok = dfs(pos+1);
if(ok) return ok;
}
return false;
}
int main(){
#ifdef LOCAL
freopen("/home/zeroxf/桌面/in.txt","r",stdin);
#endif
int n, t;
scanf("%d", &t);
for(int i = 0; i < 2000; ++i){
dis[i] = INF;
}
dis[0] = 1;
while(t--) {
scanf("%d", &n);
if(dis[n] < INF) {
printf("%d\n", dis[n]);
continue;
}
a[0] = 1;
int pos = 0;
int nn = n;
while(nn) {
pos++;
nn>>=1;
}
pos = max(pos-1,1);
for(int i = pos;; ++i) {
des = n;
depth = i;
if(dfs(0)){
printf("%d\n",i);
dis[n] = i;
break;
}
}
}
return 0;
}
|