本文主要是介绍记忆化搜索——POJ 1351，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
对应POJ题目：点击打开链接
Number of Locks
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 1123 | Accepted: 548 |
Description
In certain factory a kind of spring locks is manufactured. There are n slots (1 < n < 17, n is a natural number.) for each lock. The height of each slot may be any one of the 4 values in｛1,2,3,4｝( neglect unit ). Among the slots of a lock there are at least one pair of neighboring slots with their difference of height equal to 3 and also there are at least 3 different height values of the slots for a lock. If a batch of locks is manufactured by taking all over the 4 values for slot height and meet the two limitations above, find the number of the locks produced.
Input
There is one given data n (number of slots) on every line. At the end of all the input data is -1, which means the end of input.
Output
According to the input data, count the number of locks. Each output occupies one line. Its fore part is a repetition of the input data and then followed by a colon and a space. The last part of it is the number of the locks counted.
Sample Input
2 3 -1
Sample Output
2: 0 3: 8
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<algorithm>
#include<cstring>
#include<string>
#include<iostream>
const int MAXN=1000+10;
using namespace std;
long long num[20][5][5][2];
//num[i][j][k][e]; i表示到达第几个slot,j表示有多少种slot，k表示到达的slot的编号是（1,2,3,4），e表示是否存在相连的1和4
int n;long long dfs(int a,int b,int c,int d,int e)
{if(a==n){if(d && b>=3) return 1;else return 0;}if(num[a][b][c][d]!=-1) return num[a][b][c][d];long long ans=0;for(int i=1; i<=4; i++){int x=0;if(c==1 && i==4) x=1;else if(c==4 && i==1) x=1;int y;if((1<<(i-1))&e) y=b;else y=b+1;if(y>3) y=3;ans+=dfs(a+1, y, i, d||x, e|(1<<(i-1)));}num[a][b][c][d]=ans;return ans;
}int main()
{//freopen("in.txt","r",stdin);while(cin>>n, n!=-1){memset(num,-1,sizeof(num));long long res=dfs(0,0,0,0,0);cout<<n<<": "<<res<<endl;}return 0;
}这篇关于记忆化搜索——POJ 1351的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
