首页 > 代码库 > POJ 1351-Number of Locks（记忆化搜索）
POJ 1351-Number of Locks（记忆化搜索）
Number of Locks
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 1140 | Accepted: 559 |
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
4维的记忆化搜索。。英语太渣。。看的题解。
题意：有一排n个柱子。每个柱子的高度可以为{1,2,3,4} 求问 排列中存在相邻两个柱子高度差为3 ，且使用了至少3种高度，然后就是裸记忆化暴搜了。。题解用的状态压缩来判断当前状态使用了几种高度以及这种高度以前有没有用过。。不是太懂状态压缩，然后我觉着开标记数组也可以解决这个问题。。然后交上去A掉了发现内存耗的好多。。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <list>
#define ll long long
#define INF 0x3f3f3f3f
#define pp pair<int,int>
using namespace std;
ll dp[18][5][2][4];
bool vis[5];
int n;
ll dfs(int x,int high,bool ok,int use)
{
if(dp[x][high][ok][use]!=-1)
return dp[x][high][ok][use];
if(x==n)
{
if(use>=3&&ok)
return 1;
else
return 0;
}
ll ans=0;
for(int i=1;i<=4;i++)
{
if(!vis[i])
{
vis[i]=1;
if(ok||(high==1&&i==4)||(high==4&&i==1))
ans+=dfs(x+1,i,1,min(use+1,3));
else
ans+=dfs(x+1,i,0,min(use+1,3));
vis[i]=0;
}
else
{
if(ok||(high==1&&i==4)||(high==4&&i==1))
ans+=dfs(x+1,i,1,min(use,3));
else
ans+=dfs(x+1,i,0,min(use,3));
}
}
return dp[x][high][ok][use]=ans;
}
int main()
{
while(~scanf("%d",&n)&&n!=-1)
{
if(n<3)
{
printf("%d: 0\n",n);
continue;
}
memset(dp,-1,sizeof(dp));
dfs(0,0,0,0);
printf("%d: %lld\n",n,dp[0][0][0][0]);
}
return 0;
}POJ 1351-Number of Locks（记忆化搜索）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。