其实记忆化搜索就相当于加了记录的深搜，代码实现与爆搜非常类似，故我经常先写深搜然后硬改成睿智搜索记忆化搜索。
接苹果
分析
这题显然可以非常轻松的写出爆搜代码，但由于这样将很多的情况重复计算了很多次，会超时，故我们可以将已经计算过的情况用数组存下来，即可更快地调用。典型的记忆化搜索/dp。
以上面的思路，我们可以先写出爆搜代码，然后稍加改动即可。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int NR=1005,MXK=35;
int n,k,arr[NR],dp[NR][MXK][3];
int dfs(int t,int ch,int nw){
if(t==n)return 0;
if(dp[t][ch][nw]>-1)return dp[t][ch][nw];
int mx=0;
for(int i=1;i<=2;i++){
if(ch<(i!=nw))continue;
mx=max(mx,dfs(t+1,ch-(i!=nw),i));
}
return dp[t][ch][nw]=(mx+(arr[t]==nw));
}
int main(){
memset(dp,-1,sizeof(dp));
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)scanf("%d",arr+i);
printf("%d",dfs(0,k,1));
return 0;
}
|
分割线
蹄子剪刀布
分析
同样是记忆化搜索，这题的搜索有三个维度：局数，剩余变换次数，和当前手势。只需开一个史诗级传奇宇宙无敌超级大的数组在搜索过程中记录一下即可。记得数组下标的顺序不要搞反了（我绝对不会告诉你我因此$WA$了好多次）。
可以写一个函数，在读入的时候将每一局$fj$的手势转换成一个数字，以方便比较。
代码:
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
|
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MXN=100005;
const int MXK=25;
int n,k,dp[MXN][MXK][3];
char p[MXN];
const int win[3]={1,2,0};
inline int read(char x){
if(x=='H')return 0;
if(x=='S')return 1;
return 2;
}
int dfs(int t,int c,int nw){
if(t==n)return 0;
if(dp[t][c][nw]>-1)return dp[t][c][nw];
int mx=0;
for(int i=0;i<3;i++){
if(c-(i!=nw)<0)continue;
mx=max(mx,dfs(t+1,c-(i!=nw),i));
}
return dp[t][c][nw]=mx+(p[t]==win[nw]);
}
int main(){
memset(dp,-1,sizeof(dp));
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++){
getchar();
p[i]=read(getchar());
}
int mx=0;
for(int i=0;i<3;i++)
mx=max(mx,dfs(0,k,i));
printf("%d",mx);
return 0;
}
|
总结
- 记忆化搜索可以用爆搜的基础改，不用重写。暴（和）力（谐）万岁！（请别误解）
- 在写爆搜时，要能会选择合适的参数，以方便之后改成记忆化搜索。
文末瞎掰：
话说大家昨天看第一张黑洞的照片了吗？